5 Simple Steps for 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 video i'll walk you through 5 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 and at the end of this video we'll have a discussion of general approaches to dynamic programming beyond the examples in this video 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 here given the following sequence 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 the correct subsequence starts at 2 followed by 3 6 and 9 with a total length of 4. now one important note for this problem is that to keep things simple for now we will focus on finding the length of the sequence rather than finding the sequence itself 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 here's what the directed acyclic graph representation looks like for this particular input sequence 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 the next step for solving a dynamic programming problem is to find an appropriate sub problem a sub problem 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 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 sub problem for the sequence as lis at index 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 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 well the nice thing about this graphical visualization is that it makes it quite clear what sub problems 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 and the index 4 goes to index three and the longest increasing subsequence ending at index three has length two now the nice relationship here is that the length of the longest increasing subsequence is just going to be one plus the max over all the necessary sub problems which ends up being 3. and this should intuitively make sense right 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 four so 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 is less than 5 and the value at index k is less than the value at index five seeing this relationship in action we start at k equals zero and since the value at index zero is less than six we need to know the answers to this sub-problem and we continue to go through all possible k values less than 5 and include sub problems that satisfy the constraints laid out by the problem and in reality there's nothing special about index 5. this applies for any n so the general relationship for finding the solution to a sub problem of the longest increasing subsequence ending at index n is just one plus the max over all k that is less than n with values at index k less than values at the index n 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 sub problems from left to right so let's now implement a function let's keep track of the lengths with the list we can initialize all the lengths as one since every increasing subsequence will have at least one element then for every index from one to the length of the input list we will first find the necessary sub-problems and then we update the length according to the generalization that we have specified and then at the end we return the maximum length over the entire list of lengths that we have just updated 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 sub problems in the right order 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 sub problem more specifically if i solve the longest increasing subsequence ending at index i sub problem using the value of the longest increasing subsequence at index j i can say that the previous index of index i is index j let's look at a specific example for some clarification in this sequence the previous index of index 0 can be labeled as negative 1 since there is no previous sequence value that leads to index 0. 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 one finally index four actually only has one choice because the sub problem that's used to calculate the length at index four is the longest increasing subsequence ending at index three so the previous index is subsequently also three this type of pattern with tracking previous sub problems is a common trick used to solve dynamic programming problems let's now take a look at a more challenging problem here's the problem you're given n boxes each with the 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 so to make this more clear let's take a look at a couple examples given the following set of three boxes the answer to this problem is six the tallest possible stack is the green box on top of the blue box notice that we can 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 the following set of six boxes see if you can figure out the solution for this input i recommend pausing the video here and seeing if you can figure out the solution okay so the solution in this case actually ends up being the following stack with the red box at the bottom orange box in the middle and purple box on top we can get a total height of seven 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 all right let's get started on trying to solve this 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 here's what the graph ends up looking like if we apply the constraints between all pairs of boxes now the nice thing about this representation is 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 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 sub problem what does a partial path represent a path ending at a particular box or 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 four another example is a sub problem ending at the yellow box in which the best possible height is six there are actually two different sets of stacks with heights of six the easiest one to see is the green box on top of the yellow box and if we look at the sub problem that ends with the red box at the bottom the optimal height is seven 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 sub problem and how it works makes sense the next step from here is to find relationships among subproblems as we have done before let's take a particular sub problem and ask what sub problems 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 sub problems that are necessary are the optimal stack height ending at the orange box which we already saw was for the optimal height of stacks ending at the blue box which ended up being three and lastly 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 and 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 sub problems what's going on here is that we are taking our current sub problem 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 we first have to find the set of boxes that can actually be stacked above the blue box and then the second step involves adding the height of the blue box to the tallest stack among all sub problems we can use this relationship to now solve the sub problems one by one the last piece of the puzzle involves the order to solve the sub problems order does matter for example if you want to solve the sub problem ending at the red box we must first have the solution to the sub problem 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 sub problems 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 given the example of boxes we've already seen many times we first sort the boxes by the length giving us the following order we then define the dictionary mapping boxes to heights which are currently set to each box's own height now starting from index 1 we start with the sub problem with the purple box as the base of the stack it's pretty clear to us that there are no valid boxes that can be stacked on top of the purple box so the set of sub problems s is empty and therefore the best height of the sub problem stays at 2 containing only the height of the purple box we now move index i to equal 2 which corresponds to the orange box now we go through all the boxes before the orange box in our sorted list and find only one box that can be stacked on top of the orange box therefore the answer to this sub problem for the tallest stack that can be created with the orange box as the base is the height of the orange box plus the height of the purple box which ends up being four moving to i equals three we now look at the sub problem ending at the blue box once again the only valid box that can be stacked on top of the blue box is the purple box so the height of the tallest stack with the blue box as the base is three things get a little more interesting when we move to the sub problem with the yellow box forced to be the base now the possible boxes that can be stacked on top of the yellow box are the green box the purple box the orange box and the blue box the best height of all these sub problems is four so the height of the tallest possible stack with the yellow box as the base is six and finally moving to the last index of i equals five which corresponds to the red box the set of valid subproblems consists of the purple box orange box and the blue box the best possible height from these sub problems comes from the stack ending at the orange box with the height of four so the answer to the sub problem involving the red box ends up being the height of the red box plus 4 which is 7. at this point we have finished iterating so we return the maximum height over all of subproblems and that ends up being 7 so that is the final solution for this input 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 and 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 the most common type is as follows you're given an input sequence of length n and the subproblem involves an ordered subsequence of length i as shown here this is exactly what was the case in the longest increasing subsequence problem another similar version of a problem like this that you might encounter is a sequence of length n but given in a random order where we first have to sort the sequence in the right order and then the sub problem is an eye length subsequence this is exactly the type of sub problem we encountered in the box stacking problem some other examples of common subproblems may involve the case where you're given two sequences and the subprompt involves the appropriate subsequences of each of these sequences this is essentially a slightly more complex version of what we've seen already 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 another important subproblem structure to be aware of is when you're given a two-dimensional array or matrix as an input and 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 that's all for this video and thanks for watching if you enjoyed the content please hit the like button so that this content will be recommended to more people if you want to see more content like this please don't forget to hit the subscribe button and if you want to more directly support the work of this channel please check out the patreon page linked in the description below i'll see you on the next video

Channel: Reducible

Views: 268,629

Rating: 4.9125409 out of 5

Keywords: Dynamic Programming, Dynamic Programming problems, Dynamic Programming steps, Dynamic Programming examples, Dynamic programming algorithm

Id: aPQY__2H3tE

Length: 21min 26sec (1286 seconds)

Published: Sun Aug 16 2020