From recursion to a table

Dynamic programming is a simple idea with a frightening name: solve a sub-problem once, write its answer down, and read it from there ever after. How many ways to climb stairs taking 1 or 2 steps? You reach step n either from the step before or from two before; the ways add up.

1ways = [0] * (n + 1)
2ways[0] = 1
3ways[1] = 1
4for step in range(2, n + 1):
5    ways[step] = ways[step - 1] + ways[step - 2]
6return ways[n]

The table fills from small to large; the boxes you need when filling one are already full. ways[0] = 1 looks odd and is right: there is exactly one way to climb no steps, which is to stay put.

Every DP solution is the answer to three questions. What does one box of the table mean? How is a box worked out from smaller boxes? What are the values of the smallest boxes? You should be able to say all three in a sentence before writing code.

Tasks