Dynamic programming (DP) solves a problem by breaking it into smaller copies of itself, solving each once, and reusing the answers instead of recomputing them.
When DP applies
- Overlapping subproblems: the same smaller subproblem appears many times, so remembering pays off.
- Optimal substructure: the best full answer is built from the best sub-answers. Needed only when optimizing (min/max/fewest/cheapest).
- Overlapping alone (counting/value problems) is enough to speed things up; optimal substructure matters specifically for optimization.
Core vocabulary
- Recurrence: formula defining a value in terms of smaller values of itself.
- Base case: smallest input with a direct answer; recursion stops here. Every recursion needs one.
- Subproblem: one of the smaller copies. Fibonacci example:
fib(0)=0,fib(1)=1,fib(n)=fib(n-1)+fib(n-2).
Two techniques
| Memoization (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| Direction | Big problem down to base cases | Base cases up to big problem |
| Mechanism | Recursion + a cache (dict) | A loop filling an array dp |
| Computes | Only subproblems needed | Every subproblem in range |
| Risk | Deep recursion overflows the stack | None from recursion |
Same answer, same Big-O. Memoization = your recursion plus a cache. Tabulation avoids recursion limits and is easier to reason about for space.
The 4-step recipe (finding the recurrence)
- Define the subproblem in words as a full sentence: what does
dp[i]mean? - Write the recurrence: express
dp[i]from smaller entries. - Nail the base cases: smallest inputs with direct answers.
- Decide fill order: every entry filled after the entries it depends on (usually small to large).
Complexity
- Fibonacci plain recursion: Time O(2^n), Space O(n). With DP: Time O(n), Space O(n) (or O(1) rolling).
- Climbing stairs: same as Fibonacci; DP gives O(n) time, O(1) rolling space.
- Coin change: Time O(amount * coins), Space O(amount).
- Rule: total time = number of distinct subproblems x work per subproblem. DP computes each distinct subproblem once.
Recurrence shapes seen
- Count (Fibonacci / climbing stairs):
dp[i] = dp[i-1] + dp[i-2]. Stairs base casesdp[0]=1,dp[1]=1. - Optimize (coin change, fewest coins):
dp[a] = 1 + min(dp[a-c] for coin c <= a), basedp[0]=0. Seed cells with infinity for “unreachable”; return -1 if unreachable. - Rolling variables trick drops space to O(1) whenever each entry depends only on a fixed number of recent entries.
Gotchas
- Wrong or missing base cases poison every cell built on top.
- Wrong iteration order reads empty or stale cells; match loop direction to dependency direction.
- Off-by-one table size: to store
dp[0]..dp[n]use lengthn+1, notn. - Mutable default argument
def f(n, memo={})shares one dict across calls; usememo=Noneand build a fresh dict inside. - Forgetting the impossible case: return a sentinel (-1), not infinity.
- Top-down on very large
ncan exceed Python’s recursion limit; tabulation avoids it.