Why plain recursion can be slow
The Fibonacci rule is fib(n) = fib(n − 1) + fib(n − 2), with fib(0) = 0 and fib(1) = 1. Written as plain recursion, each call makes two more calls. The number of calls grows roughly like 1.6n: fib(30) needs over a million calls. This is exponential time.
The waste comes from solving the same subproblem again and again.
The two conditions for DP
- Overlapping subproblems: the same smaller problem appears many times.
- Optimal substructure: the best answer to the big problem is built from best answers to smaller ones.
To design DP: (1) define the state (what one table cell means), (2) write the recurrence (how a cell uses smaller cells), (3) set the base cases, (4) choose the order to fill cells, (5) read the answer.
Top-down (memoization) and bottom-up (tabulation)
Memoization (top-down)
Keep recursion but remember answers in a dictionary or array.
memo = {}
def fib(n):
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]Tabulation (bottom-up)
Fill an array from the smallest case upward with a loop.
def fib(n):
F = [0] * (n + 1)
if n > 0: F[1] = 1
for i in range(2, n + 1):
F[i] = F[i - 1] + F[i - 2]
return F[n]Both run in O(n) time instead of exponential. Tabulation uses no call stack, so it cannot overflow. The table version can even keep only the last two values: O(1) memory.
Other programming methods: greedy, backtracking, divide and conquer
- Greedy: at each step take the choice that looks best right now, never go back. Fast, but correct only for some problems (for example making change with coins 1, 2, 5, 10, or picking the most activities that do not overlap). With coins {1, 3, 4} and amount 6, greedy gives 3 coins but the best is 2.
- Divide and conquer: split into independent parts, solve each, combine (merge sort, binary search). Parts do not repeat, so no table is needed.
- Backtracking: build a solution step by step and undo a step when it cannot work (N-queens, Sudoku, generating all subsets). It explores many options and can be slow.
- DP: like divide and conquer, but the parts overlap, so save their answers.
Coin change by DP
def min_coins(coins, amount):
INF = float('inf')
best = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return best[amount]Time O(amount × number of coins).
Try it: count staircase paths
You climb a staircase taking 1 or 2 steps at a time. How many ways to reach step 6? Make a table: ways[0] = 1, ways[1] = 1, ways[i] = ways[i − 1] + ways[i − 2]. Fill it on paper (answer: 13). It is the Fibonacci pattern again. Check by running the bottom-up table in the last 3D step, then code it in Python.
Key formulas and definitions
- [object Object]
- [object Object]
- [object Object]
- [object Object]
Worked examples
1. Fill the table F[0..7] for Fibonacci.
0, 1, 1, 2, 3, 5, 8, 13. Each value is the sum of the two before it.
2. How many calls does plain recursion make for fib(5)?
Calls(0) = Calls(1) = 1. Calls(2) = 3, Calls(3) = 5, Calls(4) = 9, Calls(5) = 1 + 9 + 5 = 15.
3. With memoization, how many calls for fib(5)?
Each n from 5 down to 2 makes 2 calls the first time; total 2 × 5 − 1 = 9 calls.
4. Fewest coins for 6 with coins {1, 3, 4} by DP.
best[0..6] = 0, 1, 2, 1, 1, 2, 2. best[6] = 1 + min(best[5], best[3], best[2]) = 1 + 1 = 2 (3 + 3).
5. Staircase: 1 or 2 steps at a time, ways to reach step 5?
ways = 1, 1, 2, 3, 5, 8 for steps 0..5, so 8 ways.
6. Grid paths: moving only right or down in a 3 × 3 grid of cells (corner to corner). How many paths?
paths[i][j] = paths[i−1][j] + paths[i][j−1], first row and column = 1. Table rows: 1 1 1 / 1 2 3 / 1 3 6. Answer 6.
Common mistakes
- Using DP when subproblems do not overlap (plain divide and conquer is enough).
- Forgetting base cases, so the table starts with wrong values.
- Filling the table in the wrong order: a cell is read before it is computed.
- Trusting greedy without proof: it fails for coins {1, 3, 4} and amount 6.