In this , I gave you an introduction to Dynamic Programming with several examples. Here I will solve 6 harder Dynamic Programming problems to show you how to approach them. article Unique Paths A robot is located at the top-left corner of a grid. m x n The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there? Solution Given that the robot can only move to the right or down, we can reach the position (bottom-right corner) in two different ways: {m,n} Going to the right from (m, n -1) Going down from (m -1, n) Therefore, the total number of paths to will be the number of paths to plus the number of paths to . These two new problems are just instances of the original problem. Therefore we can use recursion to generate a solution. (m, n) (m, n-1) (m-1, n) Let's call the number of ways to reach the position (m, n). f(m,n) f( , ) = f(m,n) = n or m are outside the grid
f(m,n) = f(m , n) + f(m, n ) 0 0 1 0 if -1 -1 Recursive solution Line 5 represents the number of paths to reach any position in the first column or row of the grid (we can only reach them by going all the way right or down, therefore we return 1). We can improve upon this if we notice that many problems will be computed more than once: To compute we need and . f(m,n) f(m-1, n) f(m, n-1) For we need and . f(m-1, n) f(m-2, n) f(m-1, n-1) For we need and . f(m, n-1) f(m, n-2) f(m-1, n-1) If you suspect a problem might be solved via Dynamic Programming, I recommend drawing a tree with all possible paths to see if there are repeated subproblems. If you can derive a recursion and prove that there are repeated subproblems and optimal substructure, you can apply Dynamic Programming. Top-down Dynamic Programming Going from the recursive solution to a top-down DP solution is very straightforward. We just need to: Check if the results are already in our cache. If so, we return them. If they're not, cache them before we return. In line 8, I check if to avoid bugs like . (-1 == dp[n]) if(dp[n] = -1) Bottom-up Dynamic Programming Now, let's take a different look at the problem. From we can go right to , , etc. There is only one way to reach these positions. Similarly, there is only one way to reach all the positions in the first column: going down from . We can start building a table with this information: (0,0) (0,1) (0,2) (0,0) dp[ ][ ] = dp[i][ ] = i :m dp[ ][i] = i :n dp[i][j] = dp[i ][j] + dp[i][j ] 0 0 0 // Empty grid 0 1 for in 1 // first row 0 1 for in 1 // first col -1 -1 // Any other position follows the same logic as in the top-down approach This approach will build the full table with all possible results. We return the one we are interested in: the most bottom-right position. m*n Complexity Computing the complexity of the bottom-up approach is trivial. There are two nested loops in which the amount of work is constant, giving an overall time complexity of . The space complexity is as well. O( mn ) O(m*n*) For the top-down, it seems a bit trickier, but the logic is the same. We do constant work for every call (because we cache results) and there are calls. Therefore, the time complexity is . O(mn) O( mn ) Note: This problem can be solved in using basic mathematics. You have m rows, n columns and you can only move to the right and down (states). You can code a path using to symbolize right and for down. Then, for rows and columns you need to generate a string of elements that have 2 states: or . In this string, there will be and . This problem is equivalent to find all permutations of an array of elements (taking into account all the repetitions): O(m+n) R D m n (m-1) + (n-1) R D m-1 Ds n-1 Rs m+n-2 Unique Paths 2 A robot is located at the top-left corner of a grid (marked 'Start' in the diagram below). m x n The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and space is marked as and respectively in the grid. 1 0 Solution Try to solve this one without looking at my solution. The code (for any of the approaches I described for the previous problem) is almost the same. You only need to take into account that cells have values and some of them can be blocked. If a cell is blocked, the robot cannot visit it and therefore there are 0 ways in which the robot can reach, from a cell where the is an obstacle, the cell to its right or down. To avoid duplication, here is the code only for the bottom-up approach. Coin Change You are given coins of different denominations and a total amount of money . Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return . amount -1 You may assume that you have an infinite number of each kind of coin. Solution Recursive solution Imagine you need to solve this problem by hand. At every step, you have an of money and a few coins to choose from. Let's say the coins are , and , and the amount is . You can take three different paths: amount 1 2 5 11 Take the coin with value . You're facing now with the problem of computing the fewest number of coins that you need to get to . 1 *10* Choose the coin with value . You're facing now with the problem of computing the fewest number of coins that you need to get to . 2 *9* Take the coin with value . You're facing now with the problem of computing the fewest number of coins that you need to get to . 5 *6* Which one will produce the desired output (minimum number of coins)? At this stage, we don't know. We need to explore each path in full and return the minimum. It is pretty obvious now that we can use recursion to solve this. It should look something like this, with representing the minimum number of coins to reach . f(n) n f( ) = f(n) = ; n< f(n) = c coins, + min(f(n-c)), n> 0 0 -1 for 0 // No solution for in return 1 for 0 In : C++ Top-down Dynamic Programming From this it is trivial to get a top-down solution. You only need to add a cache, as we did in the previous problem: Bottom-up Dynamic Programming The bottom-up solution takes a different path. The idea is to fill a table with the minimum amount of coins needed to generate the values , starting from the "initial conditions": [0, amount] f(0) = 0 From , we can use one coin to get to all the values in the array . We initialize them to . 0 coins 1 Important note: You may have noticed that I have created arrays that seem to have an extra element. The entry represents the problem of reaching the amount . This is why it seems there is an offset of in the code (we return instead of because indices represent quantities). You will see this pattern in more places in this article. sol[0] 0 1 sol[amount] sol[amount -- 1] Variation How would you solve this problem if there wasn't an infinite number of each kind of coin. Coin Change 2 You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. Solution Let's review our previous example: amount = and coins = . Again, we have the same three choices. 11 [1,2,5] Take the coin with value . You're facing now with the problem of computing the fewest number of coins that you need to get to *10*. 1 Choose the coin with value . You're facing now with the problem of computing the fewest number of coins that you need to get to . 2 *9* Take the coin with value . You're facing now with the problem of computing the fewest number of coins that you need to get to . 5 *6* In this case, instead of getting the minimum of the three, we return the sum of the three paths. If we arrive to an instance where , we (it is a solution we need to count). If amount is negative, that path doesn't lead to a solution and we . amount = 0 return 1 return 0 Since this is just a variation on the previous problem, I will only write the implementation of the bottom-up approach. You have the tools to generate recursive and top-down solutions. C++ Edit Distance Given two strings and , return . word1 word2 the minimum number of operations required to convert word1 to word2 You have the following three operations permitted on a word: Insert a character Delete a character Replace a character Example: Input: = "horse", = "ros" word1 word2 Output: 3 Solution Recursive solution This problem seems tricky at first, so we need to be systematic and try to work our way into a solution from a good example. Let's take "horse" and "ros", and focus on the last character of each word: 1. If "e" and "s" were the same, we could "forget about them" and keep working with "hors" and "ro" 2. Since "e" and "s" are different, we need to make them equal. We have 3 choices: Replace "e" with "s" (or "s" with "e"), and now they're the same Delete "e" (or "s") and see and continue with the rest of the string "hors" and "ros" to see Insert a character ("s" or "e" respectively) to make the last characters equal Each possibility will generate another subproblem of smaller size, therefore we can code this recursively. We need to find the minimum of these 3 branches and return it ( , since taking any of these paths indicates that there is at least one ). plus 1 edit operation Top-down Dynamic Programming If you play around with this example you'll see that this problem has optimal substructure, so I'll just show you the code for the solution top-down here: Bottom-up Dynamic Programming And bottom-up here: Word Break Given a string and a dictionary containing a list of words, determine if can be segmented into a space-separated sequence of one or more dictionary words. non-empty s wordDict non-empty s Note: The same word in the dictionary may be reused multiple times in the segmentation.You may assume the dictionary does not contain duplicate words. Example: Input: s = " ", wordDict = ["leet", "code"] leetcode Output: true Solution Recursive solution This problem has a relatively straightforward solution. If we were to solve this by hand, we would start taking prefixes of our input and see if they belong to our dictionary. As soon as we find one, we repeat the process with the remaining of the string. In other words, we solve a smaller instance of the same problem. Let's try to define the recursion first and later see if there are overlapping subproblems. f( ) = f(s) = every prefix p (and correspondent suffix x) s: any f(p) == , f(s) = f(x)\ all f(p) == , f(s) = "" true // if the string is empty, it can be decomposed using the words in wordDict for in if true if false false Let's use the following example to illustrate this algorithm: s=dogsandcats
dict=[and,dog, dogs, cats] We start taking prefixes of until we find one that belongs to dict. In this case, the first prefix that meets this condition is . s dog Our new string s' is "andcats". Repeating 1 we get to sand. Now, s" is "cats". The prefix cats belongs to the dictionary. Since s"' is empty, we return true. This snippet of code solves this problem recursively: Top-down Dynamic Programming Coming back to the example, you can see that bot "dogs" + "and" and "dog" + "sand" produce the same suffix: "cat". There are overlapping subproblems and we can use . memoization Bottom-up Dynamic Programming The bottom-up approach builds a table, where the empty string is initialized to true and every other entry to false. From there, the logic is the same: We build the solution for all the substrings of s, from length to the length of . This is why we have a loop in the range (both inclusive, since they represent the number of characters we're considering at each step) and another internal loop in the range to move around all prefixes for that length 0 s [1,n] [i-1,0] If the problem has a solution for the prefix (this is represented by ), we "follow the recursion" on the suffix ): if this is a valid word, there is a solution for the problem represented by s[0,j] dp[j] s[j+1,: dp[i] This is harder to explain in words than in code, so here it is: Conclusions As we have seen, dynamic programming problems can be solved in a systematic way: Start with small examples and see if their solution can be derived from smaller instances of the same problem. If so, recursion is a natural choice. Draw a tree with the possible paths you can take depending on the available choices. If you reach the same parameters more than once, you can improve your solution using a cache. From the recursion, arriving at a top-down solution is mechanical: you just need to add a cache. The bottom-up approach generates a table based on "the initial conditions" for the recursion. I hope you found this article helpful. I recommend sharing it with a friend or the rest of the community because you could help someone pass their exams or their next job interview. For more content, visit , and connect with me on . my blog Twitter Previously published at https://www.yourdevopsguy.com/6-hard-dynamic-programming-problems-made-easy/

Initialized

Twitter

About Bitcoin and Merkle Trees

How to Solve 6 Dynamic Programming Problems In a Systematic Way

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

13 Ways to Traverse a Tree: Recursion vs Iteration

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

13 Ways to Traverse a Tree: Recursion vs Iteration

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps