- Write a function with a base case and a recursive step and trace the call stack
- Recognise when a problem can be solved by DP and set up its recurrence
- Fill knapsack and LCS tables and recover the optimal solution
- Show when a greedy algorithm fails
If you program the Fibonacci numbers straight from F(n) = F(n − 1) + F(n − 2), the computer makes over a hundred million function calls for F(40). Add just a few lines and the same program finds F(90) instantly. In this lesson we learn how this “magic” — dynamic programming — works, starting from its foundation, recursion.
Recursion and the call stack
A function solving a problem by means of a smaller copy of itself. Every recursive function has two parts: the base case (the answer is known directly and the recursion stops) and the recursive step (the problem is shrunk towards the base case).
- n · (n − 1)!recursive step
- 0! = 1base case
The function fact(n) returns 1 when n == 0 and n * fact(n - 1) otherwise. What happens on the stack when fact(4) is called?
Show solutionHide solution
fact(4) → fact(3) → fact(2) → fact(1) → fact(0) = 1 — the base case, with 5 frames on the stack.
Ascent (frames close in reverse order):
fact(1) = 1 · 1 = 1
fact(2) = 2 · 1 = 2
fact(3) = 3 · 2 = 6
fact(4) = 4 · 6 = 24.
Time O(n) and stack memory O(n) — every call waits on the stack until its answer arrives.
Overlapping subproblems and memoisation
Plain recursive Fibonacci makes fib(5) call fib(3) twice and fib(2) three times — the same subproblems are solved over and over. The number of calls grows exponentially, just like the answer: calls(n) = 2F(n + 1) − 1. Memoisation (top-down) stores each subproblem's answer in a dictionary and never computes it twice; tabulation (bottom-up) fills the answers from small to large with a loop.
- T(n)running time of plain recursive fib(n)
- φthe golden ratio
With memoisation each fib(k) is computed once: n + 1 subproblems × O(1) work = O(n). From exponential to linear!
from functools import lru_cache
calls = 0
def fib_naive(n):
global calls
calls += 1
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
def fib_table(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_naive(25), 'naive calls:', calls)
print(fib_memo(25), 'memo calls:', fib_memo.cache_info().misses)
print(fib_table(90))▸ Expected output
75025 naive calls: 242785 75025 memo calls: 26 2880067194370816120
lru_cache only 26 distinct subproblems are computed. The table version finds F(90) instantly with O(1) memory.Classic DP: knapsack and LCS
0/1 knapsack: choose items with weights wᵢ and values vᵢ for a bag of capacity W so that the total value is maximal (each item is either taken or not). For item i there are two choices — skip it or take it; we keep the better one.
- dp[i][c]best value using the first i items with capacity c
- wᵢ, vᵢweight and value of item i (the second option only if wᵢ ≤ c)
Time and memory O(n · W). This is pseudo-polynomial: exponential in the number of bits of W.
W = 5. Items (weight, value): 1: (1, 1), 2: (2, 3), 3: (3, 4), 4: (4, 5). Find the maximum value and the chosen items.
Show solutionHide solution
i = 1: [0, 1, 1, 1, 1, 1]
i = 2: [0, 1, 3, 4, 4, 4] (e.g. c = 3: max(1, dp[1][1] + 3 = 4) = 4)
i = 3: [0, 1, 3, 4, 5, 7] (c = 5: max(4, dp[2][2] + 4 = 7) = 7)
i = 4: [0, 1, 3, 4, 5, 7] (c = 5: max(7, dp[3][1] + 5 = 6) = 7)
Answer dp[4][5] = 7.
Recovery: dp[4][5] = dp[3][5] → item 4 not taken; dp[3][5] = 7 ≠ dp[2][5] = 4 → item 3 taken, c = 5 − 3 = 2; dp[2][2] = 3 ≠ dp[1][2] = 1 → item 2 taken, c = 0.
Choice: items 2 and 3 (weight 2 + 3 = 5, value 3 + 4 = 7).
def knapsack(items, W):
n = len(items)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i, (w, v) in enumerate(items, start=1):
for c in range(W + 1):
dp[i][c] = dp[i - 1][c]
if w <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
chosen, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i - 1][c]:
chosen.append(i)
c -= items[i - 1][0]
return dp[n][W], sorted(chosen), dp
best, chosen, dp = knapsack([(1, 1), (2, 3), (3, 4), (4, 5)], 5)
for row in dp:
print(row)
print('best value:', best, '| items:', chosen)▸ Expected output
[0, 0, 0, 0, 0, 0] [0, 1, 1, 1, 1, 1] [0, 1, 3, 4, 4, 4] [0, 1, 3, 4, 5, 7] [0, 1, 3, 4, 5, 7] best value: 7 | items: [2, 3]
Longest common subsequence (LCS): the longest sequence of characters that appears in both strings in the same order (not necessarily side by side). For “ABCBDAB” and “BDCABA” the LCS has length 4, for example “BCBA”. LCS underlies file comparison in diff and git and the alignment of DNA sequences.
- L[i][j]LCS length of the first i characters of a and the first j of b
- L[0][j] = L[i][0]0 (nothing in common with an empty string)
Time O(m · n): two strings of length 1000 need only 10⁶ cells, while checking all subsequences would mean 2¹⁰⁰⁰ options.
def lcs(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
out, i, j = [], len(a), len(b)
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return dp[-1][-1], ''.join(reversed(out))
print(lcs('ABCBDAB', 'BDCABA'))
print(lcs('AGGTAB', 'GXTXAYB'))▸ Expected output
(4, 'BCBA') (4, 'GTAB')
Greedy or DP?
A greedy algorithm makes the choice that looks best at the moment and never goes back. It is fast and simple, but correct only for problems with the “greedy-choice property”: Kruskal, Dijkstra, Huffman coding, the fractional knapsack. DP compares all options without repetition and is correct wherever there are optimal substructure and overlapping subproblems.
- coins[x]fewest coins that make the amount x
- can available coin value
Coins {1, 3, 4}, amount 6. How many coins does the greedy algorithm (always the largest coin) use? What is optimal?
Show solutionHide solution
DP table coins[0 … 6]:
coins[1] = 1, coins[2] = 2, coins[3] = 1, coins[4] = 1,
coins[5] = 1 + min(coins[4], coins[2], coins[1]) = 1 + 1 = 2,
coins[6] = 1 + min(coins[5], coins[3], coins[2]) = 1 + 1 = 2.
Optimal: 2 coins (3 + 3). “Take the largest” in the first step closed off the right path.
def min_coins(coins, amount):
dp = [0] + [float('inf')] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount], dp
def greedy_coins(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return count
best, table = min_coins([1, 3, 4], 6)
print('greedy:', greedy_coins([1, 3, 4], 6), '| DP:', best, '| table:', table)
print('greedy:', greedy_coins([1, 5, 6, 9], 11), '| DP:', min_coins([1, 5, 6, 9], 11)[0])▸ Expected output
greedy: 3 | DP: 2 | table: [0, 1, 2, 1, 1, 2, 2] greedy: 3 | DP: 2
| Approach | Idea | When it is correct | Example |
|---|---|---|---|
| Divide and conquer | independent subproblems | subproblems do not repeat | merge sort |
| Dynamic programming | remember answers to repeated subproblems | optimal substructure + overlapping subproblems | knapsack, LCS, coins |
| Greedy | always the locally best choice | the greedy-choice property is proven | Kruskal, Dijkstra, Huffman |
Key points
- Recursion needs a base case and a step that approaches it; each call takes a frame on the stack.
- Plain recursive Fibonacci is Θ(φⁿ); with memoisation or a table it is O(n).
- DP needs optimal substructure and overlapping subproblems; recipe: state, transition, base, order.
- 0/1 knapsack is O(nW), LCS is O(mn); the solution is recovered by walking back through the table.
- Greedy is fast but optimal only with the greedy-choice property ({1, 3, 4} for 6: 2 coins, not 3).
Check yourself
10 questions. Every correct answer earns XP.