Why start with grids#
Dynamic programming is usually taught with an array and an index, which is abstract enough that the idea hides behind the notation. A grid is the same idea where you can see it: the table is the board, and filling it in is something you could do by hand on paper.
The rule#
You are at the bottom right and you could only have arrived from above or from the left. That one sentence gives the whole recurrence.
- For the cheapest route:
best[r][c] = grid[r][c] + min(above, left) - For the number of routes:
ways[r][c] = above + left
Same shape, different combining step. Minimum when the question asks for the best route, sum when it asks how many there are. Once you spot that, the two problems are one problem.
Fill order is the whole technique#
Each cell needs the cell above it and the cell to its left. Go top to bottom and left to right, and both are always finished before you need them.
That is the difference between dynamic programming and recursion with a cache. The recursion asks for an answer and works it out if it is missing; this puts them in an order where nothing is ever missing. Same answers, no call stack, and on a grid the order is obvious.
Edges without special cases#
The first row can only be reached from the left, and the first column only from above. It is tempting to write separate loops for them, and that is where the bugs are.
Treat anything off the grid as the identity instead: 0 when you are adding, infinity when you are taking a minimum. Then one line handles every cell, edges included.
What the table costs#
Rows times columns, and a constant amount of work per cell. The number of routes it counts can be astronomical (a 15 by 15 grid has about 40 million) and none of them are ever built. Each cell is worked out once and reused by the two cells it feeds, and that reuse is where the saving comes from.
Only two rows are ever live at once, so if memory is tight you can keep one row and overwrite it as you go. Worth knowing; not worth doing until the full table is working.
Not greedy#
Stepping toward the cheaper neighbour fails, and it is worth seeing why once:
1 8 6
0 9 1
3 9 0
Greedy takes the 0 below the start and gets walled in by nines, paying 13. Going right across the top costs 11. Paying the 8 early is what makes it cheap, and nothing local could have told you that.
Greedy commits at each step. Dynamic programming commits to nothing until every cell is known.
Where the shape turns up again#
- Edit distance between two strings: a grid where one string is the rows and the other the columns.
- Longest common subsequence: the same grid, a different combining step.
- Knapsack: items down the side, capacity across the top.
None of those look like a board, and all of them fill a two-dimensional table where each entry depends on its neighbours. Learning the mechanics here, where you can draw it, makes those read as variations instead of new subjects.
Practice in order#
- Minimum path sum, which is the recurrence at its plainest.
- Unique paths with obstacles, the same table with addition instead of a minimum, and a zero where the board is blocked.
- Climbing stairs, which is this in one dimension, and worth doing afterwards to see that a grid was never the point.