A Practical Guide to Solving Dynamic Programming Problems |

Dynamic programming is one of the most powerful algorithmic techniques in computer science. The basic premise centers around the idea of solving a problem by first identifying and solving subproblems, and then bringing these sub-problems together in some manner to solve the larger problem. Not surprisingly, this process is easier said than done. In fact, dynamic programming problems can be notoriously challenging to wrap your head around.

In this article, I'll walk you through five key steps that you can use to help tackle dynamic programming problems and show you how they work in the context of two specific problems. The first problem is a pretty fundamental one, while the second one is a more challenging extension. At the end of this article, we'll have a discussion of general approaches to dynamic programming beyond the examples provided.

The Longest Increasing Subsequence Problem

Let's get started. The first example we'll look at is the longest increasing subsequence problem. Let's say you're given a sequence of n elements, and you want to find the length of the longest increasing subsequence. An increasing subsequence is just a sequence of elements where each subsequent element has both a larger value and index than the previous element.

Here are some examples to clarify what I mean. Given the following sequence:

[10, 9, 1, 2, 5, 3, 7, 101, 18]

The longest increasing subsequence is 1 followed by 2 followed by 5, with a total length of 3.

Now that the problem is more clear, take a second to see if you can find the longest increasing subsequence and its respective length for the following sequence:

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

The correct subsequence starts at 2 followed by 3, 6, and 9, with a total length of 4.

Note: To keep things simple for now, we will focus on finding the length of the sequence rather than finding the sequence itself.

Step 1: Visualize Examples

The first step in solving dynamic programming problems is to find a way to visualize examples. Visualization is a great way to see connections and underlying patterns in the problem that can later be relevant to the solution. When solving this particular problem, we clearly have some restrictions on valid sequences, so it makes sense to find a way to diagram out what makes a valid sequence.

A nice model that shows up all the time in dynamic programming is the directed acyclic graph. Imagine each element of the sequence is a node in a graph, and we construct a directed edge from one node to another if the node on the right contains a larger value. What's nice about this representation is that an increasing subsequence is just another path in the graph. In fact, going one step deeper, the length of the longest increasing subsequence corresponds to a length of the longest path in this directed acyclic graph plus one (since we are technically counting nodes). Solving this particular problem might be a little bit more clear, and sometimes this shift in perspective is the key to making challenging problems more approachable.

Step 2: Find an Appropriate Subproblem

The next step for solving a dynamic programming problem is to find an appropriate subproblem. A subproblem is basically a simpler version of our overall problem. Finding subproblems can be tricky, but let's focus on what we know about this problem. We know the longest increasing subsequence is going to be a particular subset of our initial sequence. One way to specify this subset is through the starting point and the ending point. Every increasing subsequence, no matter how long, will have a starting and ending point within the original sequence.

So, let's modify one of these variables to create a sub-problem. It turns out that you can solve this particular problem with either choice, but I personally find focusing on the ending point of a subsequence as a little bit more intuitive. Let's define a subproblem for the sequence as lis[k], which would mean the longest increasing subsequence ending at index k. For example, the lis ending at 3 would be the sequence starting at 1 followed by 2, which has a length of 2. Remember that when I am referring to lis in this particular problem, it is specifically with respect to the length of the sequence.

Step 3: Find Relationships Among Subproblems

Okay, so now that we've identified one possible subproblem, the third step requires finding relationships among sub-problems. It often helps to ask yourself questions in this phase. For example, suppose you want to solve the sub-problem of finding the longest increasing subsequence ending at index 4. What subproblems are necessary to solve this?

The nice thing about the graphical visualization is that it makes it quite clear what subproblems we need. One path through index 4 must go through index 0, so we will need to know the length of the longest increasing subsequence ending at index 0, which happens to be 1. Another path comes through index 1, so we'll need that subproblem as well, which also has length 1. The final possible path to index 4 goes through index 3, and the longest increasing subsequence ending at index 3 has length 2.

The nice relationship here is that the length of the longest increasing subsequence is just going to be 1 + max(all necessary subproblems), which ends up being 3. This should intuitively make sense. If I want to find the longest increasing subsequence ending at index 4, it does make sense that I would just add 1 to the longest increasing subsequence over all subsequences that eventually arrive at index 4.

Step 4: Generalize the Relationship

Once you've found a reasonable relationship among subproblems, we want to then generalize this relationship. Let's look at our other example and see if we can come up with a similar process to solve the longest increasing subsequence ending at index 5. The key idea here is that we're going to choose subproblems ending at index k if and only if k < 5 and the value at index k is less than the value at index 5.

Seeing this relationship in action, we start at k = 0, and since the value at index 0 is less than 6, we need to know the answer to this sub-problem. We continue to go through all possible k values less than 5 and include subproblems that satisfy the constraints laid out by the problem. In reality, there's nothing special about index 5; this applies for any n.

The general relationship for finding the solution to a subproblem of the longest increasing subsequence ending at index n is just 1 + max(lis[k]) for all k < n where value[k] < value[n].

Step 5: Implementation

Now we are ready for implementation, which is the final step. Implementing a dynamic programming solution is just a matter of solving subproblems in the appropriate order. What's most important is that before solving a particular subproblem, all the necessary prerequisite subproblems have been solved. In this problem, the order is actually fairly straightforward: we have to solve the subproblems from left to right.

Let's now implement a function. ```python def longestincreasingsubsequence(inputlist): # Keep track of the lengths with a list lengths = [1] * len(inputlist) # Initialize all lengths as 1

# For every index from 1 to the length of the input list
for i in range(1, len(input_list)):
    # Find the necessary sub-problems
    subproblems = [lengths[j] for j in range(i) if input_list[j] < input_list[i]]

    # Update the length according to the generalization
    if subproblems:
        lengths[i] = 1 + max(subproblems)

# Return the maximum length over the entire list of lengths
return max(lengths) if lengths else 0

There are many ways to implement this function, so don't get too bogged down in the details. The important thing to remember here is the thought process we use to identify and solve the subproblems in the right order.

### Finding the Actual Subsequence

There's one last important question we should address. Everything we have done so far has been specifically with respect to finding the length of the longest increasing subsequence, but how do we actually find the underlying sequence? The key idea here is actually fairly simple. All we have to do is keep track of the previous indices for a particular subproblem. More specifically, if I solve the longest increasing subsequence ending at index `i` subproblem using the value of the longest increasing subsequence at index `j`, I can say that the previous index of `i` is `j`.

Let's look at a specific example for some clarification. In a sequence, the previous index of index 0 can be labeled as -1, since there is no previous sequence value that leads to index 0. The same can be said about the previous index of index 1. For index 2, the previous index is either index 0 or index 1, and it doesn't really matter which one we choose since they both have the same length values. For the previous index at index 3, there's only one choice: index 1. Finally, index 4 actually only has one choice because the subproblem that's used to calculate the length at index 4 is the longest increasing subsequence ending at index 3, so the previous index is subsequently also 3. This type of pattern with tracking previous subproblems is a common trick used to solve dynamic programming problems.

### A More Challenging Problem: The Box Stacking Problem

Let's now take a look at a more challenging problem. You're given `n` boxes, each with a length, width, and height. Your goal is to find the height of the tallest possible stack of boxes, with the constraint that a box can only be stacked on top of another if its length and width are both smaller. Another assumption that we will make to simplify things is that boxes cannot be rotated at any point during the process of stacking.

To make this more clear, let's take a look at a couple of examples. Given the following set of three boxes, the answer to this problem is 6. The tallest possible stack is the green box on top of the blue box. Notice that we cannot stack the red and green boxes on top of one another since it does not satisfy the constraint given in the problem.

Now, as an exercise, given a set of six boxes, see if you can figure out the solution. I recommend taking a moment here to see if you can figure out the solution. The solution, in this case, actually ends up being a stack with the red box at the bottom, the orange box in the middle, and the purple box on top. We can get a total height of over 6, which is the best we can do. Make sure you take a second to verify that this is indeed the only solution to this problem for the given input.

### Visualizing the Box Problem

The first step, as before, is to visualize examples. A lot of times in dynamic programming type problems, there can be a lot of information thrown at you, and it's sometimes helpful to focus on one aspect of the problem at a time. When solving a problem like this, it might help to first visualize the particular constraint given for stacking boxes. After all, before we even figure out what's the tallest possible stack, it makes sense to first identify which boxes are able to be stacked on top of one another.

Once again, the concept of directed acyclic graphs is really helpful here for visualization purposes. Let's connect a directed edge between two boxes if the box on the left can be stacked on top of the box on the right. The nice thing about this representation is that paths in this directed acyclic graph have a nice intuitive meaning: every path in the graph corresponds to a stack of boxes. Now the goal is just to find the path that gives the greatest height.

### Defining the Subproblem for Box Stacking

So now that we have a good way of visualizing the problem, our next step is to figure out an appropriate sub-problem. This is another reason I love looking at directed acyclic representations of dynamic programming problems. If our final goal is to find the path with the tallest stack, it makes sense that partial paths should be a reasonable subproblem.

What does a partial path represent? A path ending at a particular box, or a partial path, essentially means a stack where we force that box to be the base of the stack. Therefore, our sub-problem that naturally arises from this idea is to find the best possible height of a stack of boxes with a given box forced to be at the bottom. This will allow us to find optimal partial paths in this graph, which will then build into the eventual optimal path.

Here are some examples of instances of these subproblems:
- The subproblem in which the orange box is the base has a stack with a maximum height of 4.
- Another example is a subproblem ending at the yellow box, in which the best possible height is 6. There are actually two different sets of stacks with heights of 6. The easiest one to see is the green box on top of the yellow box.
- If we look at the subproblem that ends with the red box at the bottom, the optimal height is 7, which is also the tallest possible stack for the set of boxes we've seen.

Take a second to make sure the formulation of the subproblem and how it works makes sense.

### Finding Relationships and Generalizing

The next step from here is to find relationships among subproblems. As we have done before, let's take a particular subproblem and ask what subproblems are needed to solve it. For example, if we want to find the optimal height of a stack of boxes ending at the red box, we have three boxes that directly lead to the red box. So the subproblems that are necessary are:
- The optimal stack height ending at the orange box (which we already saw was 4).
- The optimal height of stacks ending at the blue box (which ended up being 3).
- The optimal stack ending at the purple box (which happens to only be 2, since no other box can be stacked on top of it).

The next question is then, if we know the answers to these subproblems, how do we get the solution to the optimal height of stacks with the red box as the bottom? The answer to this is actually fairly intuitive: we simply add the height of the red box to the maximum height of all the necessary subproblems. What's going on here is that we are taking our current subproblem, finding all the necessary prerequisite subproblems, picking the best one out of those, and adding the height of the current box to the best height so far.

Let's generalize this relationship. Given a new set of boxes, let's ask ourselves how do we solve the optimal height of a stack with the blue box as the base. There are two steps involved here:
1. First, we have to find the set of boxes that can actually be stacked above the blue box.
2. Then, the second step involves adding the height of the blue box to the tallest stack among all those subproblems.

We can use this relationship to now solve the subproblems one by one.

### Implementation and Ordering

The last piece of the puzzle involves the order to solve the subproblems. Order does matter. For example, if you want to solve the subproblem ending at the red box, we must first have the solution to the subproblem ending at the orange box. So the next question is then, how do we ensure a correct ordering if boxes are given to us in a completely random order?

Well, we know that the boxes that can be stacked on top of each other are entirely dependent on the length and width of the boxes, with larger lengths and widths generally being able to have more boxes stacked on top of them. Therefore, a natural way to ensure we solve subproblems in the correct order is to first sort boxes by length or width. With this final piece in place, we are now ready to implement the solution.

Given a list of boxes, we will first sort the boxes by their length. Just so we are clear, it doesn't matter if we sort them by length or width; either one works. Then, to organize a mapping between subproblems and their respective heights, we will construct a dictionary that maps each box to the tallest stack height possible with that box as the base of the stack. We can initialize this dictionary with each box mapped to its own height.

Then, we iterate through indices from 1 to the number of boxes, select a specific box, and then find the set of boxes that can be stacked above the current box. We can define a helper function `can_be_stacked()` which will essentially do a quick check based on the given constraint. Now, following the general relationship that we have defined, the tallest stack with the current box as the base will be the sum of the current box height with the maximum height over the set of identified sub-problems. After iterating through and solving all the sub-problems, the tallest stack is simply the maximum height found amongst all sub-problems.

Again, this is just one of the many ways to solve the problem. The code for this problem has a lot of parts, so it's worth breaking it down to see how it really works.

### Common Subproblem Patterns

This problem at first looks pretty challenging, but following the steps greatly helped us narrow our focus and simplify the problem. And that's what ends up happening in a lot of dynamic programming problems. In many ways, the hardest part of dynamic programming problems is organizing the given information in the right way to identify the correct subproblem. That's the part that requires a lot of practice and creativity in problem-solving.

There is no doubt that finding the right subproblem can be the most challenging aspect of dynamic programming. I want to take a second to look at some of the most common subproblems you will encounter while solving these types of problems.

*   **Ordered Subsequence:** You're given an input sequence of length `n`, and the subproblem involves an ordered subsequence of length `i`. This is exactly what was the case in the longest increasing subsequence problem.
*   **Sorted Subsequence:** A similar version is a sequence of length `n` given in a random order, where we first have to sort the sequence, and then the subproblem is an `i`-length subsequence. This is exactly the type of subproblem we encountered in the box stacking problem.
*   **Two Sequences:** Some other examples of common subproblems may involve the case where you're given two sequences, and the subproblem involves the appropriate subsequences of each of these sequences. This is essentially a slightly more complex version of what we've seen already.
*   **Expanding from the Middle:** A more unique type of subproblem may involve a sequence of inputs where the right sub-problem is actually to expand from the middle of the sequence outwards. These types of sub-problems are not as common as the other examples, but they are worth noting.
*   **2D Matrix/Grid:** Another important subproblem structure to be aware of is when you're given a two-dimensional array or matrix as an input. The most common sub-problem for this type of input is basically a sub-matrix of some dimension less than the input dimensions.

These are the most common sub-problems I've seen in my experience, and hopefully, that will give you some direction when you're stuck in a particularly challenging dynamic programming problem. At the end of the day, though, nothing beats practicing experience. The best way to improve your dynamic programming skills is through a lot of diligent work with problems and examples.