6 Hard Dynamic Programming Problems Made Easy

In this article, 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.

Unique Paths

A robot is located at the top-left corner of a m x n grid

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 {m,n} (bottom-right corner) in two different ways:

• Going to the right from (m, n -1)
• Going down from (m -1, n)

Therefore, the total number of paths to (m, n) will be the number of paths to (m, n-1) plus the number of paths to (m-1, n). These two new problems are just instances of the original problem. Therefore we can use recursion to generate a solution.

Let's call f(m,n) the number of ways to reach the position (m, n).

f(0,0) = 1\
f(m,n) = 0 if n or m are outside the grid\
f(m,n) = f(m-1, n) + f(m, n-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 f(m,n) we need f(m-1, n) and f(m, n-1).
• For f(m-1, n) we need f(m-2, n) and f(m-1, n-1).
• For f(m, n-1) we need f(m, n-2) and f(m-1, n-1).

If you suspect a problem might be solved via Dynamic Programming problems, 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 (-1 == dp[n]) to avoid bugs like if(dp[n] = -1).

Bottoum-up Dynamic Programming

Now, let's take a different look at the problem. From (0,0) we can go right to (0,1), (0,2), 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 (0,0). We can start building a table with this information:

dp[0][0] = 0 // Empty grid
dp[i][0] = 1 for i in 1:m // first row
dp[0][i] = 1 for i in 1:n // first col
dp[i][j] = dp[i-1][j] + dp[i][j-1] // Any other position follows the same logic as in the top-down approach

This approach will build the full m*n table with all possible results. We return the one we are interested in: the most bottom-right position.

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 O(mn). The space complexity is O(m*n*) as well.

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 O(mn) calls. Therefore, the time complexity is O(mn).

Note:

This problem can be solved in O(m+n) 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 R to symbolize right and D for down. Then, for m rows and n columns you need to generate a string of (m-1) + (n-1) elements that have 2 states: R or D. In this string, there will be m-1 Ds and n-1 Rs. This problem is equivalent to find all permutations of an array of m+n-2 elements (taking into account all the repetitions):

Unique Paths 2

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

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 1 and 0 respectively in the grid.

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 amount. 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 -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 amount of money and a few coins to choose from. Let's say the coins are 1,2 and 5, and the amount is 11. You can take three different paths:

1. Take the coin with value 1. You're facing now with the problem of computing the fewest number of coins that you need to get to 10.
2. Choose the coin with value 2. You're facing now with the problem of computing the fewest number of coins that you need to get to 9.
3. Take the coin with value 5. You're facing now with the problem of computing the fewest number of coins that you need to get to 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 f(n) representing the minimum number of coins to reach n

f(0) = 0
f(n) = -1; for n<0 // No solution
f(n) = for c in coins, return 1 + min(f(n-c)), for n>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 [0, amount], starting from the "initial conditions":

• f(0) = 0
• From 0, we can use one coin to get to all the values in the array coins. We initialize them to 1.

Important note:

You may have noticed that I have created arrays that seem to have an extra element. The entry sol[0] represents the problem of reaching the amount 0. This is why it seems there is an offset of 1 in the code (we return sol[amount] instead of sol[amount -- 1] because indices represent quantities). You will see this pattern in more places in this article.

Variation:

• How would you solve this problem if there 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 = 11 and coins = [1,2,5]. Again, we have the same three choices.

1. Take the coin with value 1. You're facing now with the problem of computing the fewest number of coins that you need to get to 10.
2. Choose the coin with value 2. You're facing now with the problem of computing the fewest number of coins that you need to get to 9.
3. Take the coin with value 5. You're facing now with the problem of computing the fewest number of coins that you need to get to 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 amount = 0, we return 1 (it is a solution we need to count). If amount is negative, that path doesn't lead to a solution and we return 0.

Since this is just a variation on the previous problem, I will only write the C++ implementation of the bottom-up approach. You have the tools to generate recursive and top-down solutions.

Edit Distance

Given two strings word1 and word2, return 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: word1 = "horse", word2 = "ros"
• 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:

• If "e" and "s" were the same, we could "forget about them" and keep working with "hors" and "ro"
• 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 (plus 1, since taking any of these paths indicates that there is at least one 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 non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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 = "leetcode", wordDict = ["leet", "code"]
• 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("") = true // if the string is empty, it can be decomposed using the words in wordDict\
f(s) = for every prefix p (and correspondent suffix x) in s:\
    if any f(p) == true, f(s) = f(x)\
    if all f(p) == false, f(s) = false

Let's use the following example to illustrate this algorithm:

s=dogsandcats
dict=[and,dog, dogs, cats]

1. We start taking prefixes of s until we find one that belongs to dict. In this case, the first prefix that meets this condition is dog.
2. Our new string s' is "andcats". Repeating 1 we get to sand.
3. Now, s" is "cats". The prefix cats belongs to the dictionary.
4. 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 0 to the length of s. This is why we have a loop in the range 1,n and another internal loop in the range [i-1,0] to move around all prefixes for that length
• If the problem has a solution for the prefix s0,j, we "follow the recursion" on the suffix s[j+1,:): if this is a valid word, there is a solution for the problem represented by 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:

1. 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.
2. 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.
3. From the recursion, arriving at a top-down solution is mechanical: you just need to add a cache.
4. 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 my blog, and connect with me on Twitter.