All You Need to Know About Dynamic Programming

What is dynamic programming and why should you care about it? In this article, I will introduce the concept of dynamic programming, developed by Richard Bellman in the 1950s, a powerful algorithm design technique to solve problems by breaking them down into smaller problems, storing their solutions, and combining these to get to the solution of the original problem. The hardest problems asked in FAANG coding interviews usually fall under this category. It is likely that you will get tasked with solving one during your interviews, hence the importance of knowing this technique. I will explain what dynamic programming is, give you a recipe to tackle dynamic programming problems, and will take you through a few examples so that you can understand better when and how to apply it. As I already did in my previous post about , I will share my thought process when solving problems that can be solved using this methodology, so that you can do the same when you face one of them. I don’t want you to memorize anything. You need to understand the technique and practice to acquire the skill of turning ideas into code. Coding is not about learning programming languages. It is about analyzing a problem, considering different solutions, choosing the best one, and then implementing it in some programming language. coding interviews Dynamic programming Dynamic programming is a general technique for solving optimization, search and counting problems that can be decomposed into subproblems. To apply dynamic programming, the problem present the following two attributes: must Optimal substructure Overlapping subproblems Optimal substructure A problem has optimal substructure if the optimal solution to a problem of size n can be derived from the optimal solution of the same instance of that problem of size smaller than n. For example, if the shortest path to go from Paris to Moscow goes through Berlin, it will be made of the shortest path from Paris to Berlin and the shortest path from Berlin to Moscow. If a problem can be solved by combining optimal solutions to subproblems, the strategy is called . This is why merge sort and quick sort are not classified as dynamic programming problems. non-overlapping divide and conquer Overlapping subproblems Let’s take an example you’re probably familiar with, the Fibonacci numbers, where every number is the sum of the previous two Fibonacci numbers. The Fibonacci series can be expressed as: F( ) = F( ) = F(n) = F(n ) + F(n ) 0 1 1 -1 -2 They say a picture is worth a thousand words, so here it is (from Elements of programming interviews): To solve F(n), you need to solve F(n-1) and F(n-2), but F(n-1) needs F(n-2) and F(n-3). F(n-2) is repeated, coming from two different instances of the same problem – computing Fibonacci number. a This can be expressed in a recursive function: To solve a problem of size n, you call the same function to solve an instance of the same problem, but of a smaller size. You keep calling the function until you hit a , in this example, n = 0 or n = 1. base case This leads us to the relationship between recursion and dynamic programming. Recursion and dynamic programming Conceptually dynamic programming involves recursion. You want to solve your problem based on smaller instances of the same problem, and recursion is a natural way of expressing this in code. The difference with a pure recursive function is that we will trade space for time: we will store the optimal solution to the subproblems to be able to efficiently find the optimal solution to the problem that we originally wanted to solve. This is not to say that you must use recursion to solve dynamic programming problems. There is also an iterative way of coding a dynamic programming solution. Bottom-up dynamic programming You need to fill a table with the solution to all the subproblems (starting from the base cases) and use it to build the solution you are looking for. This is done in an iterative fashion, using one of the following: A multidimensional array (1D too) – the most commonly used. A hash table. A binary search tree. as your data structure to store the solutions to the subproblems. Top-down dynamic programming Code the recursive algorithm and add a cache layer to avoid repeating function calls. This will all be much clearer when we start with the examples. How to attack a dynamic programming problem Optimal substructure and overlapping subproblems are the two attributes a problem must have to be solved used dynamic programming. You will need to verify this when your intuition tells you dynamic programming might be a viable solution. Let’s try to get a feel for what kind of problems can be solved using dynamic programming. Things that start with “find”: The first n elements that… All ways to… In how many ways … The n-th … The most optimal way… The minimum/maximum/shortest path … Are potential . candidates Steps to solve a dynamic programming problem Unfortunately, there is no universal recipe to solve a dynamic programming problem. You need to go through many problems until you start getting the hang of it. Do not get discouraged. This is hard. Maybe the hardest type of problems you will face in an interview. This is about modeling a problem with relatively simple tools – no need for fancy data structures or algorithms. I have solved tons of them and still, sometimes I find it difficult to get to the solution. The more you practice, the easier it will be. This is the closest to a recipe to solve dynamic programming problems: Prove overlapping subproblems and suboptimal structure properties. Define subproblems. Define recursion. Code your top-down or bottom-up dynamic programming solution. Complexity analysis varies from problem to problem, but in general, the time complexity can be expressed as: Time ~ Number of subproblems * time per subproblem It is straightforward to compute the space complexity for a bottom-up solution since it is equal to the space required to store solutions to the subproblems (multidimensional array). Examples I’ve categorized some problems according to the number of independent dimensions involved. This is not necessary, but something that I have found it useful to have a mental model to follow when designing a solution. You will see , as you code more and more. This is one of them (which I have not found explicitly described anywhere else). Use it if you find it helpful. patterns 1D problems Fibonacci Since by now you are very familiar with this problem, I am just going to present the recursive solution: { (n == || n == ) ; fib(n - ) + fib(n - ); } } int fib ( n) int if 0 1 return 1 else return 1 2 Going from recursive to top-down is usually mechanical: Check if the value you need is already in the cache. If so, return it. Otherwise, cache your solution before returning. { cache(n + , ); fib_helper(n, cache); } { ( != cache[n]) cache[n]; (n == || n == ) cache[n] = ; cache[n] = fib_helper(n - , cache) + fib_helper(n - , cache); cache[n]; } int fib ( n) int vector int 1 -1 return int fib_helper ( n, &cache) int vector int if -1 return if 0 1 1 else 1 2 return And here, the bottom-up solution, where we build a table (from the base cases) to form the solution to the problem we’re looking for. This table is a 1D array: we only need to store the solution to a smaller version of the same problem to be able to derive the solution to the original problem. { f(n + , ); f[ ] = ; ( i = ; i <= n; i++) f[i] = f[i - ] + f[i - ]; f[n]; } int fib ( n) int vector int 1 0 1 1 for int 2 1 2 return Extra space optimization This approach could be further optimized in memory, not time (there are faster techniques to compute Fibonacci numbers, but that is a topic for another article), by using just 3 variables instead of an array since we only need to keep track of 2 values, f(n-1) and f(n-2), to produce the output we want, f(n). { (n == || n == ) ; n1= , n2 = , f = ; ( i = ; i <= n; i++) { f= n1 + n2; n2 = n1; n1 = f; } f; } int fib ( n) int if 0 1 return 1 //Variables that represent f(n - 1), f(n - 2) and f(n) int 1 1 0 for int 2 return This is more advance, but a common pattern. If you only need to keep track of: A few variables, you might be able to get rid of the 1D array and turn it into a few variables. A few rows in a 2D matrix, you might be able to reduce it to a couple of 1D arrays. Etc. By reducing dimensions we improve our space complexity. For now, you can forget about this, but after you get some practice, try to come up with these optimizations yourself to increase your ability to analyze problems and turn your ideas into code. In an interview, I would just go for the simpler version, just discussing potential optimizations and only implementing them if there is enough time after coding your “standard” dynamic programming solution. Climbing stairs You are climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top: 1 step + 1 step and 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top: 1 step + 1 step + 1 step, 1 step + 2 steps and 2 steps + 1 step Solution Try to solve this problem on your own. You might be able to come up with a recursive solution. Go through my explanation and the previous examples to see if you can code a top-down solution. A little hint: The fact that the question starts with , should already make you think of a potential candidate for dynamic programming. “In how many ways” In this case, you want to reach step N. You can reach step number N from step N – 1 or N – 2 because you can jump 1 or 2 steps at a time. If you can solve these two subproblems, you can find the solution to the general problem. Let’s call f(N) the number of ways you can get to step N. To get f(N), you need f(N – 1) and f(N – 2). To get to f(N – 1), you need f(N- 2) and f(N – 3). For f(N – 2), you need f(N – 3) and f(N – 4). I don’t need to continue. You can already see that: This problem has overlapping subproblems: you’ll need to compute multiple times f(N – 2), f(N – 3), f(N – 4), … This problem presents optimal substructure: with the optimal solution to f(N – 1) and f(N – 2), you can get the optimal solution to f(N). which means dynamic programming can be used to solve it. I will not write the code for this problem because … I have already done it in the previous example! You can write and test your solution . here Longest increasing subarray Given an unsorted array of integers, find the length of the longest increasing subsequence. For example, for [10,9,2,5,3,7,101,18] the output would be 4, for the sequence [2,3,7,101] Solution We need to find the length of the increasing subsequence for an array of size n. This sounds like an optimization problem, which could be a candidate for dynamic programming, so let’s try. Imagine that you already have the solution for a problem of size N – let’s call it s(n) – and you add an extra element to the array, called Y. Can you reuse part of the solution to X to solve this new problem? This mental experiment usually gives some good insight into the problem. longest In this case, you need to know if the new element can extend one of the existing sequences: Iterate through every element in the array, let’s call it X. If the new element Y is greater than X, the sequence can be extended by one element. If we have stored the solution to all the subproblems, getting the new length is trivial – just a lookup in an array. We can generate the solution to the new problem from the optimal solution to the subproblems. Return the length of the new longest increasing subsequence. We seem to have an algorithm. Let’s continue our analysis: : we’ve verified that the optimal solution to a problem of size n can be computed from the optimal solution to the subproblems. Optimal substructure : To compute s(n), I’ll need s(0), s(1), …, s(n-1). In turn, for s(n-1), I’ll need s(0), s(1), …, s(n-2). The same problems needs to be computed multiple times. Overlapping subproblems Here’s the code for the bottom-up solution. { (nums.empty()) ; dp(nums.size(), ); maxSol = ; ( i = ; i nums[j]){ dp[i] = max(dp[i], dp[j] + ); } } maxSol = max(maxSol, dp[i]); } maxSol; } int lengthOfLIS ( & nums) const vector int if return 0 vector int 1 int 1 for int 0 for int 0 if 1 return You can write and test your solution . here How many BST Given n, how many structurally unique BSTs (binary search trees) that store values 1 … n? Example: Input: 5 Output: 42 Explanation: Given n = 5, there are a total of 42 unique BST’s Solution Let’s go through that example. Let’s imagine we have numbers the numbers 1,2,3,4,5. How can I define a BST? The only thing I really need to do is to pick one of the numbers as the root. Let’s say that element is number 3. I will have: 3 as root Numbers 1 and 2 to the left of 3. Numbers 4 and 5 to the right of 3. I can solve the same subproblem for (1,2) – let’s call this solution L – and (4,5) – let’s call this solution R – and count how many BST can be formed with 3 as its root, which is the product L * R. If we do this for every possible root and add all the results up, we have our solution, C(n). As you can see, being methodical and working from a few good examples helps design your algorithms. In fact, this is all that needs to be done: Pick an element as the root of the BST. Solve the same problem for numbers (1 to root – 1) and (root + 1 to n). Multiply both the results for each . subproblem Add this to our running total. Move to the next root. In fact, we don’t really care what numbers lie in each side of the array. We just need the size of the subtrees, i.e. the number of elements to the left and to the right of the root. Every instance of this problem will produce the same result. In our previous example, L is the solution to C(2) and so is R. We only need to compute C(2) once, cache it, and reuse it. { dp(n + , ); dp[ ] = ; dp[ ] = ; ( i = ; i <= n; ++i){ ( j = ; j < i; ++j){ dp[i] += dp[j] * dp[i - - j]; } } dp.back(); } int numTrees ( n) int vector int 1 0 0 1 1 1 for int 2 for int 0 1 return You can code and test your solution . here 2D problems These problems are usually a little harder to model because they involve two dimensions. A common example is a problem where you have to iterate through two strings or to move through a map. The top-down solution is not much different: find the recursion and use a cache (in this case, your key will be based on 2 “indices”) For the bottom-up, a 2D array will suffice to store the results. This might be reduced one or a couple of 1D arrays as I mentioned before, but don’t stress about this. I’m just mentioning it in case you see it when solving a problem. As I said in my other article, learning is iterative. First, focus on understanding the basics and add more and more details little by little. Minimum path sum Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only at any point in time. move either down or right Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. Solution should make you think of dynamic programming. Let’s analyze this further. We can get from any cell C with indices (i,j) (that is not on the top or left border) from cells A = (i-1, j) and B = (i,j-1). From this, we can see that some problems are going to be computed multiple times. Also, we if know the optimal solution to A and B, we can compute the optimal solution to the current cell as min(sol(A), sol(B)) + 1 – since we can only get to the current cell form A or B and we need one extra step to move from these cells to the current cell. In other words, this problem presents optimal substructure and overlapping problems. We can use dynamic programming. Minimizes Here’s the bottom-up solution. { nrow = grid.size(); (nrow == ) ; ncol = grid[ ].size(); > minSum(nrow, (ncol, )); minSum[ ][ ] = grid[ ][ ]; ( col = ; col >& grid) const vector vector int const int if 0 return 0 const int 0 vector vector int vector int 0 0 0 0 0 for int 1 0 0 1 0 for int 1 0 1 0 0 for int 1 for int 1 1 1 return 1 1 The boundary conditions are defined over the border of the matrix. You can only get to the elements in the border in one way: moving one square to the right or down from the previous element. You can code and test your solution . here Knapsack problem Given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that the sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property). Solution Try to come up with a recursive solution. From there, add a cache layer and you’ll have a top-down dynamic programming solution! The main idea is that, for every item, we have two choices: We can add the item to the bag (If it fits), increase our total value, and decrease the capacity of the bag. We can skip that item, keep the same value, and the same capacity. After we’ve gone through every single combination, we just need to pick the max value. This is extremely slow, but it’s the first step towards a solution. Having to decide between two options (add an element to a set or skip it) is a very common pattern that you will see in many problems, so it’s worth knowing it and understanding when and how to apply it. { (n == || W == ) ; (wt[n - ] > W) knapSack(W, wt, val, n - ); max(val[n - ] + knapSack(W - wt[n - ], wt, val, n - ), knapSack(W, wt, val, n - )); } // Recursive. Try to turn this into a piece of top-down DP code. int knapSack ( W, wt[], val[], n) int int int int if 0 0 return 0 if 1 return 1 else return 1 1 1 1 A bottom-up solution is presented here: { i, w; K[n + ][W + ]; (i = ; i <= n; i++) { (w = ; w <= W; w++) { (i == || w == ) K[i][w] = ; (wt[i - ] <= w) K[i][w] = max( val[i - ] + K[i - ][w - wt[i - ]], K[i - ][w]); K[i][w] = K[i - ][w]; } } K[n][W]; } // C style, in case you are not familiar with C++ vectors int knapSack ( W, wt[], val[], n) int int int int int int 1 1 for 0 for 0 if 0 0 0 else if 1 1 1 1 1 else 1 return Longest common subsequence (LCS) Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0. Example: Input: text1 = “abcde”, text2 = “ace” Output: 3 Explanation: The longest common subsequence is “ace” and its length is 3. Solution Again, compute the X makes me think that dynamic programming could help here. longest Since you already have some experience with dynamic programming, I’ll go straight to the 2 properties, from the example. Let’s call the strings A and B, and our solution to this problem f(A, B). The idea is to see whether the 2 last characters are equal: If so, the LCS has at least length 1. We need to call f(A[0:n-1], B[0:n-1]) to find the LCS till that index, and add 1 because A[n] and B[n] are the same. If not, we remove that last character from both strings -one at a time – and find which path produces the LCS. In other words, we take the maximum of f(A[0: n -1], B) and f(A, B[0:n-1]) : Let’s see what calls can we expect: (“abcde”, “ace”) produces x1 = (“abcd”, “ace”) and y1 = (“abcde”, “ac”); x1 will produce x12 = (“abc”, “ace”) and y12= (“abcd”, “ac”); y1 will produce (“abcd”, “ac”) and (“abcde”, “a”). As you can see, the problems same problems need to be computed multiple times. Overlapping subproblems : Very similar to the longest increasing subsequence. If we add one extra character to one of the strings, A’, we can quickly compute the solution from all the cached results that we obtained from solving for A and B. Optimal substructure Using examples to prove things is not the way you start a mathematical demonstration, but for a coding interview is more than enough. { n = text1.length(); m = text2.length(); > dp(n + , (m + , )); ( i = ; i <= n; i++){ ( j = ; j <= m; j++){ (text1[i ] == text2[j ]) dp[i][j] = dp[i ][j ]+ ; dp[i][j] = max(dp[i ][j], dp[i][j ]); } } dp[n][m]; } int longestCommonSubsequence ( &text1, &text2) const string const string const int const int vector vector int 1 vector int 1 0 for int 1 for int 1 if -1 -1 -1 -1 1 else -1 -1 return You can code and test your solution . here More resources For more exercises, check the resources I listed in my previous article. For more dynamic programming specific content, the following videos are a great place to start. They get in more detail and cover other problems I have purposely not addressed here to give you more variety. Also, check out the . Wikipedia article for DP Conclusion You need to become familiar with these problems because many others are just variations on these. But do not memorize them. Understand when and how to apply dynamic programming, and practice until you can easily turn your ideas into working code. As you have seen, it is about being methodical. You don’t need advanced knowledge of algorithms or data structures to solve the problems. Arrays are enough. I have not completed a time/space analysis. That is an exercise for you. Feel free to reach out with questions or comments. PS: I hope you found this useful. If so, share this article because you can help someone else, visit my blog , and connect with me on . www.yourdevopsguy.com Twitter Previously published at https://www.yourdevopsguy.com/all-you-need-to-know-about-dynamic-programming/

All You Need to Know About Dynamic Programming

Too Long; Didn't Read

Company Mentioned

@yourdevopsguy

RELATED STORIES