Dynamic Programming: An induction approach

Dynamic Programming (DP) is a generic programming technique that uses memorisation in order to solve problems that can be broken down into smaller problems of the same type.

Richard Bellman was the first to coin its name. He wanted to study these kind of problems back in the 1950s while he was in the US Air Force. The problem is that the Air Force at the time did not want to spend money funding mathematical research. To get around that, Bellman came up with a meaningless name (Dynamic Programming) so that he could continue working on it secretly as apparently nobody would question or try to really understand what that new term was all about. More info about that story can be found in this excellent MIT lesson¹.

Richard Bellman

This post shows a general strategy to tackle DP problems using mathematical induction. It comes down to these 3 steps:

1. Write down a formula that describes the solution of the problem as a “mix” of subproblems of the same type. By “mix” I mean using some sort of logic. Sometimes a simple addition/subtraction/multiplication will be enough. Other times you might need to define a separate function. In induction terms this is called the hypothesis.
2. Compute all the initial happy cases, ie, the cases that don’t require knowledge of the subproblems to be solved. In induction terms this is called the base case.
3. Apply the formula you found in step 1 to the remaining cases that were not in 2.

It is better to illustrate the above with an example. Let’s solve a classic DP problem: Finding the shortest path on a grid.

In the image bellow, we want to find the shortest path between the top-left corner of the grid to the bottom-right corner.

Original grid. The blue cell represents the starting pointing of the path and the red cell the ending. Let’s assume our grid indexes start at 1 and go until ’n’ (the # of rows) and ‘m’ (the # of columns)

The only moves allowed are from top to bottom and from left to right.

Valid moves for an arbitrary cell.

Each time you visit a cell, you increase your path number by the amount in that cell. For example, if you decide to go to the red cell by first going through the first row and then going down the last column, your cost would be 5+3+2+1+(-2)+7+4+(-3)+2+7+2=28. The problem asks you to find what is the minimum cost to get to the red cell given the moving restrictions above.

We have a few strategies to solve this:

1. Brute force

This approach simply tests ALL possible paths. Whenever the algorithm reaches the red cell, it checks if that is the shortest path found so far. The complexity of this algorithm is O(n+m)! where ‘n’ is the number of rows and ‘m’ is the number or columns of the grid².

2. Backtracking

This is just a bit better than Brute force. In Brute force the algorithm only stops when it reaches the bottom-right corner of the grid. Backtracking is a bit smarter. There is no need to continue down the path if the current sum is already larger than then smallest path currently known. The complexity of this algorithm is also O(n+m)! since in the worst case, no backtracking is performed and the algorithm needs to check every path until the end, just like brute force.

3. Dynamic programming

In order to find a DP algorithm that solves this problem, let’s follow our recipe. First, let’s define the solution as a “mix” of subproblems. Let’s assume that we have the solution for a certain 2x2 sub-grid (this is our induction hypnotises):

A small section of the shortestPath grid. Do not mistake this with the standard grid. The shortestPath grid keeps track of the shortestPath from cell [1, 1] to cell [x, y]. The shortestPath from the blue cell (not shown in the picture) to the cell [u, v] is 100. Likewise, the shortestPaths from the blue cell to [u, v+1] and [u+1, v] are 115 and 120. With that info we can calculate the shortestPath between the blue cell to [u+1, v+1]. Here ‘u’ and ‘v’ are indexes.

In the image above, we know that the shortest path from the top-left corner (the blue cell) to the [u, v] cell is 100. Likewise, the shortest path from the top-left corner to the cell [u+1, v] is 120 and the one in [u, v+1] is 115. You are probably wondering HOW we got these numbers. For now just assume we magically have them (ie, that is our induction hypothesis). Well, in order to find the shortest path to the cell [u+1, v+1] we only have 2 options: either the path is coming from above (ie, from cell [u, v+1]) or from the left (ie, from cell [u+1, v]) because we only allow moves from left to right and from top to bottom. We know both the shortest paths from the cell above and from the cell on the left (115 and 120). Therefore, we just need to choose the one that has the shortest path so far (115) and sum the value of the cell [u+1, v+1] itself. That yields us that the shortest path from the top-left corner to cell [u+1, v+1] is 115 + grid[u+1, v+1]. We can mathematically equate the above:

shortestPath[u+1][v+1] = min(shortestPath[u][v+1],
                             shortestPath[u+1][v]) + grid[u+1][v+1]

We have our recursive formula that step 1 requires. Now, let’s go to step 2, ie, find the happy cases.

Notice that shortestPath[0, 0] = grid[0, 0] (you started in the top-left corner and arrived in the top-left corner. Therefore the cost is only the value of ‘grid’ in that coordinate).

shortestPath[0][0] = grid[0][0];

We can now calculate the value of shortestPath[0, 1]. Since we are in the top of the grid, the only way to arrive in cell [0, 1] is from cell [0, 0]. Therefore shortestPath[0, 1] = shortestPath[0, 0] + grid[0, 1] = 5 + 3 = 8. We can then go to the next cell, [0, 2]. The same idea applies, ie, shortestPath[0, 2] = shortestPath[0, 1] + g[0, 2] = 8 + 2 = 10. In fact, yon can do that for the whole first row of the grid:

//'m': The number of columns in the grid
for(int k=2; k<=m; k++){
   shortestPath[1][k] = shortestPath[1][k-1] + grid[1][k];
}

And we can use the same idea to fill the first column of the grid:

//'n': The number of rows in the grid
for(int k=2; k<=n; k++){
   shortestPath[k][1] = shortestPath[k-1][1] + grid[k][1];
}

Once we’ve done the above, we have our happy cases (ie, our induction base case) done:

Here is a picture of what we have so far:

shortestPath grid. The happy cases have been found. Again, do not mistake this with the standard grid. This is the grid where the memorisation happens. The original grid remains intact.

Now we can go to step 3, ie, apply the general formula until we get our answer:

for(int i=2; i<=n; i++){
   for(int j=2; j<=m; j++){
      shortestPath[i][j] = min(shortestPath[i-1][j],
                               shortestPath[i][j-1]) + grid[i][j];
   }
}

In the end, your answer will be in shortestPath[n][m], where ’n’ is the number of rows in your grid and ‘m’ the number of columns.

Notice the complexity of this algorithm is just O(n*m). Dynamic Programming algorithms will usually yield polynomial time complexities.

In the next article we are going to solve a more interesting problem. Stay tuned!

Sources:

1. “Optimization problems” by MIT OpenCourseware: https://www.youtube.com/watch?v=uK5yvoXnkSk (24:11)
2. “Counting paths on a grid” by Art of Problem Solving: https://www.youtube.com/watch?v=M8BYckxI8_U