Dynamic Programming
Solve each small problem once.
Dynamic programming sounds intimidating, but it's just two ideas you've already met. Break a problem into smaller versions of itself, like recursion. And save each answer, so you never solve the same small problem twice, like memoization.

- Sounds scary
- Smaller versions of the problem
- Save each answer
Two styles
There are two styles. Top down starts with the big problem, recurses into smaller ones, and caches the answers, exactly like our fast Fibonacci. Bottom up starts with the tiniest problems, and fills in a table, step by step, until it reaches the big one. Both give the same answers, in the same Big O.
Fibonacci, bottom up
Here's Fibonacci, bottom up. We start a table with the first two answers, zero and one. Each new entry is the sum of the two before it. No recursion, no cache, just a loop. Run it. Fib of ninety is instant.
def fib(n):
table = [0, 1]
for i in range(2, n + 1):
table.append(table[i - 1] + table[i - 2])
return table[n]
print(fib(10), fib(90))55 2880067194370816120
Summary
Dynamic programming solves each small problem once, top down with a cache, or bottom up with a table. Next, a classic. Climbing stairs.
Key takeaways- Smaller problems
- Save each answer
- Top down or bottom up