What is dynamic programming, and how do you recognise a problem that suits it?
Dynamic programming is a way of solving a problem by breaking it into smaller versions of the same problem and remembering the answers so that each one is worked out only once.
So how do you recognise a problem that suits it? There are four things to look for.
what to look for what it means
------------------------------------- ----------------------------
the problem repeats itself the same question comes up
again and again
the repeats depend on each other they are all the same shape
the answers overlap two questions need the same
answer
there are only so many states the number of states is small
enough to keep
And the classic example is the number of paths through a grid. You can move right or down. The number of paths to a cell is the sum of the paths to the cell above it and the paths to the cell on the left, and every cell asks those two questions, so the same work is done again and again.
def count_paths(rows, cols):
table = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if r == 0 or c == 0:
table[r][c] = 1
else:
table[r][c] = table[r - 1][c] + table[r][c - 1]
return table[rows - 1][cols - 1]
And the difference between the two ways of doing it is worth knowing about. Without dynamic programming the answer is worked out again and again, and the number of calls grows very fast. With it each cell is worked out once, so the answer takes O of rows times cols time instead of something exponential.
the grid size the naive calls the calls with dynamic programming
--------------- ---------------- ------------------------------
3 by 3 25 9
10 by 10 2047 100
20 by 20 about 2 million 400
And there are the two names for the two versions. Memoization is the top-down one, where you write the recursion and you add the memory. Tabulation is the bottom-up one, where you fill in a table in order. The next two questions in this topic show both.
So the rule to remember is this. If the same question comes up again and again, then work it out once and remember it.
The next two questions in this topic show the memoized version and when to prefer it.