Dynamic Programming solves a problem by combining the answers to overlapping subproblems. Two conditions signal DP: optimal substructure (the best answer is built from best answers to subproblems) and overlapping subproblems (the same subproblem is solved many times). You store each subproblem's answer so it is computed only once.
State, recurrence, base case
Every DP is three things: a state (what a subproblem is, e.g. dp[i] = best using the first i items), a recurrence (how a state is built from smaller ones), and base cases. Then either memoise (top-down) or tabulate (bottom-up).
Climbing stairs (ways to reach step n, 1 or 2 at a time)
dp[0] = 1; dp[1] = 1
for i = 2 to n:
dp[i] = dp[i-1] + dp[i-2] // last step was 1 or 2
return dp[n]O(n)→O(n) (or O(1))
Each state computed once; space can drop to O(1) keeping two values.
⚡ The edge
- Suspect DP when a problem asks for an optimal count, min or max and the brute-force recursion recomputes the same subproblems (like naive fibonacci).
- Nail three things and the code follows: the state, the recurrence, the base case. Memoise the recursion, or fill a table bottom-up.
Worked example
How many ways to climb 4 stairs taking 1 or 2 steps at a time?
- Let dp[i] be the ways to reach step i. To reach i, the last move was a 1 (from i-1) or a 2 (from i-2), so dp[i] = dp[i-1] + dp[i-2].
- Base: dp[0]=1, dp[1]=1. Then dp[2]=2, dp[3]=3, dp[4]=5.
- It's the Fibonacci pattern — 5 ways.
Answer: 5 ways (dp[i] = dp[i-1] + dp[i-2])
Worked example
Why is memoised fibonacci O(n) while naive is O(2^n)?
- Naive fib(n) recomputes fib(n-1) and fib(n-2), and those recompute the same values exponentially often.
- Memoisation stores each fib(k) the first time, so later calls are O(1) lookups.
- With n distinct values each computed once, the total is O(n).
Answer: Caching makes each of the n subproblems compute once -> O(n)
⚠ Watch out
- The hardest step is defining the state — get that right and the recurrence usually follows.
- Get the base cases and the fill order correct, or the table reads uninitialised values.
- DP needs overlapping subproblems; if subproblems are all distinct, plain recursion or greedy may be better.