How many ways are there to climb a staircase of 30 steps taking one or two steps at a time? A naive recursive solution takes two lines: the ways to reach step n are the ways to reach step n − 1 plus the ways to reach step n − 2. Run as it is, however, this function makes more than a million calls for n = 30, and for n = 50 it does not finish in reasonable time. With a small change it answers instantly even for n = 500.
That change is the central idea of dynamic programming (DP): never compute the same thing twice. The name, introduced by Richard Bellman in the 1950s, has nothing to do with computer programming in the modern sense nor with anything «dynamic»: it refers to a technique for planning in stages.
The two conditions
Dynamic programming works when the problem has two properties.
Optimal substructure: the optimal solution of the problem is built from the optimal solutions of smaller subproblems. For example, if the shortest route from Milan to Rome passes through Bologna, its Milan–Bologna stretch is in turn the shortest route between those two cities.
Overlapping subproblems: the same subproblems appear many times. On the staircase, the number of ways to reach step 10 is needed both for step 11 and for step 12. If subproblems do not repeat, as in merge sort, we speak of «divide and conquer» and DP brings no advantage.
Memoization: top-down
The first way to apply DP is to keep the natural recursion and add a cache of results already computed:
from functools import lru_cache
@lru_cache(maxsize=None)
def ways(n):
if n <= 1:
return 1
return ways(n - 1) + ways(n - 2)
Each value of n is computed only once; subsequent calls read the result from the cache. The cost drops from exponential to linear. This approach is called memoization and it is the easiest to obtain starting from a correct recursion.
The drawback is recursion depth: for very large n the stack limit is exceeded.
Tabulation: bottom-up
The second way is to fill a table starting from the smallest cases, in an order that guarantees every value needed is already available:
def ways(n):
a, b = 1, 1 # ways for steps 0 and 1
for _ in range(n - 1):
a, b = b, a + b
return b if n >= 1 else 1
Here the table shrinks to two variables, because each value depends only on the two before it. This memory reduction is common: if a row of the table depends only on the previous one, keeping two rows is enough.
| Aspect | Memoization | Tabulation |
|---|---|---|
| Order of computation | decided by the recursion | decided by the programmer |
| Subproblems computed | only those needed | all those in the table |
| Risk of stack overflow | yes | no |
| Memory optimisation | difficult | often simple |
A five-step method
When tackling a new problem it pays to follow the same scheme every time.
- Define the state: what is the minimum information that describes a subproblem? For the staircase, the step number is enough. Other problems need two or three indices.
- Write the recurrence: how is the value of a state obtained from the values of smaller states?
- Set the base cases: the subproblems small enough for the answer to be known directly.
- Choose the order of computation: states must be solved after those they depend on. In graph terms, the dependencies between states form a DAG, and the order of computation is a topological sort of it.
- Rebuild the solution: besides the optimal value, you often need the choice that achieves it. For each state, store which option gave the best result, and at the end follow the chain back.
An optimisation example: change with the fewest coins
A vending machine must give R cents in change using coins of certain denominations and wants to use as few as possible. State: the amount r. Recurrence: coins(r) = 1 + the minimum of coins(r − d) over every denomination d ≤ r. Base case: coins(0) = 0.
With denominations of 1, 3 and 4 and change of 6, the greedy approach takes the largest coin first (4) and then two 1s, three coins in total. DP finds 3 + 3 instead, two coins. It is a typical example in which the choice that looks best locally is not the optimal one, and DP, by systematically examining every subproblem, is not fooled.
Where you meet it
Dynamic programming is everywhere in computing: comparing texts and file versions, spell checkers, speech recognition with the Viterbi algorithm, aligning genetic sequences, shortest paths such as Bellman-Ford and Floyd-Warshall, knapsack and cutting problems, grammar parsing, planning stocks and investments over time.
In short
- DP applies when there is optimal substructure and there are overlapping subproblems.
- Memoization adds a cache to an already correct recursion.
- Tabulation fills a table bottom-up and avoids the limits of recursion.
- State, recurrence, base cases, order and reconstruction are the five steps to follow.
- Where greedy choices fail, DP examines every alternative without repeating work.
