@yourdevopsguyYour DevOps Guy
Software engineer: previously at Amazon and now at eBay. Certified Professional Cloud Architect.
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.
A robot is located at the topleft 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 bottomright 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}
(bottomright 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, n1)
plus the number of paths to
(m1, 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(m1, n) + f(m, n1)
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(m1, n)
and
f(m, n1)
.
 For
f(m1, n)
we need
f(m2, n)
and
f(m1, n1)
.
 For
f(m, n1)
we need
f(m, n2)
and
f(m1, n1)
.
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.
Going from the recursive solution to a topdown 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)
.
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[i1][j] + dp[i][j1] // Any other position follows the same logic as in the topdown approach
This approach will build the full
m*n
table with all possible results. We return the one we are interested in: the most bottomright position.
Complexity
Computing the complexity of the bottomup 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 topdown, 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
(m1) + (n1)
elements that have 2 states:
R
or
D
. In this string, there will be
m1 Ds
and
n1 Rs
. This problem is equivalent to find all permutations of an array of
m+n2
elements (taking into account all the repetitions):
A robot is located at the topleft 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 bottomright 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 bottomup approach.
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
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:
 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*
.
 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*
.
 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(nc)), for n>0
In
C++
:
Topdown Dynamic Programming
From this it is trivial to get a topdown solution. You only need to add a cache, as we did in the previous problem:
Bottomup Dynamic Programming
The bottomup 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 wasn’t an infinite number of each kind of coin.
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.
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*.
 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*
.
 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 bottomup approach. You have the tools to generate recursive and topdown solutions.
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:
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 (
plus 1
, since taking any of these paths indicates that there is at least one edit operation).
Topdown 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 topdown here:
Bottomup Dynamic Programming
And bottomup here:
Given a nonempty string s and a dictionary wordDict containing a list of nonempty words, determine if s can be segmented into a spaceseparated 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:
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]
 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.
 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:
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.
The bottomup 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]
(both inclusive, since they represent the number of characters we’re considering at each step) and another internal loop in the range
[i1,0]
to move around all prefixes for that length
 If the problem has a solution for the prefix
s[0,j]
(this is represented by
dp[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:
 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 topdown solution is mechanical: you just need to add a cache.
 The bottomup 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.
Previously published at https://www.yourdevopsguy.com/6harddynamicprogrammingproblemsmadeeasy/
Tags
Create your free account to unlock your custom reading experience.