Dynamic Programming: From Recursion to a Table
Dynamic programming turns an exponential recursion into a table of reused answers. Fibonacci drops from 2.7 million calls to 31, then coin change, counting ways, LCS and knapsack, all run.
Dynamic programming solves a problem by breaking it into overlapping subproblems with optimal substructure, computing each subproblem's answer once and reusing it. Fibonacci(30) takes 2,692,537 calls by plain recursion and 31 with memoisation. Interviewers expect the recipe: define the state, write the recurrence, set base cases, then fill a table in dependency order.
Dynamic programming applies when a problem breaks into overlapping subproblems with an optimal-substructure property. Store each subproblem's answer once and reuse it. Fibonacci(30) takes 2,692,537 calls by plain recursion and 31 with memoisation. Most DP problems are solved by defining the state, writing the recurrence, then filling a table.
- Dynamic programming applies when a problem has overlapping subproblems and optimal substructure, meaning the best answer is built from best answers to smaller pieces.
- Computing fib(30) by plain recursion made 2,692,537 calls, while the memoised version executed only 31 calls, one per distinct value.
- Top-down memoisation in Python hit RecursionError for n = 5000 under the default recursion limit of 1,000, while bottom-up tabulation has no call-stack depth problem.
- Minimum coin change uses the recurrence dp[a] = min(dp[a - c] + 1) and runs in O(amount x number of coins) time and O(amount) space.
- With coins 1, 3, 4 and amount 6, greedy picks 4 + 1 + 1 for three coins, while dynamic programming finds 3 + 3 for two.
- In a one-dimensional 0/1 knapsack table, iterating capacity downward uses each item once; iterating upward reuses items and solves the unbounded knapsack instead.
01Why plain recursion explodes
calls = 0
def fib(n):
global calls; calls += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib(30), calls) # 832040 2692537Computing the 30th Fibonacci number made 2,692,537 calls. fib(28) is computed inside fib(29) and again inside fib(30), and the repetition compounds down the tree, so the cost grows exponentially with n. There are only 31 distinct values to compute (fib(0) to fib(30)). The waste is recomputing them.
Two properties tell you DP applies: overlapping subproblems (the same ones recur) and optimal substructure (the best answer is built from best answers to smaller pieces).
02Top-down: memoisation
from functools import lru_cache
calls = 0
@lru_cache(None)
def fibm(n):
global calls; calls += 1
return n if n < 2 else fibm(n - 1) + fibm(n - 2)
print(fibm(30), calls) # 832040 31Same answer, 31 function bodies executed instead of 2.7 million. Each distinct n is computed once and later requests return the stored value. Top-down is the easiest way to start because you write the recurrence naturally and let the cache handle reuse. The cost is recursion depth: calling this version for n = 5000 raised RecursionError in my test with Python's default limit of 1,000.
03Bottom-up: tabulation
def fibt(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fibt(30)) # 832040The loop builds each value from the previous ones, so there is no call stack and no depth problem. fibt(5000) runs fine. Note the space saving: Fibonacci only needs the last two values, so two variables replace a whole table. Many DP tables can be shrunk the same way when row i depends only on row i-1.
A workable recipe for any DP problem: (1) define what a state means, (2) write the recurrence relating it to smaller states, (3) set the base cases, (4) pick an order that computes dependencies first, (5) read the answer from the final state.
04Example 1: minimum coins
def coin(coins, amt):
INF = amt + 1
dp = [0] + [INF] * amt
for a in range(1, amt + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amt] if dp[amt] <= amt else -1
print(coin([1, 5, 10, 25], 63)) # 6
print(coin([1, 3, 4], 6)) # 2
print(coin([2], 3)) # -1The recurrence is dp[a] = min(dp[a - c] + 1) over every coin c that fits. 63 takes 6 coins (25, 25, 10, 1, 1, 1). Amount 3 with only a 2-coin is impossible, so it returns -1. Time is O(amount x number of coins).
This is also a case where greedy fails. Always taking the biggest coin works for the coins 1, 5, 10, 25, but with coins 1, 3, 4 and amount 6 greedy picks 4 + 1 + 1 (three coins) while DP finds 3 + 3 (two). If a greedy rule is not provably correct, try DP.
05Example 2: counting ways
def ways(coins, amt):
dp = [1] + [0] * amt
for c in coins: # coins in the outer loop
for a in range(c, amt + 1):
dp[a] += dp[a - c]
return dp[amt]
print(ways([1, 2, 5], 5)) # 4There are 4 ways to make 5 from coins 1, 2 and 5: 5; 2+2+1; 2+1+1+1; and 1+1+1+1+1. Putting the coins in the outer loop counts each combination once. Swapping the loops (amount outside, coins inside) would count 2+1+... and 1+2+... as different orders, which answers a different question. This is a classic place for subtle bugs, so say which one you mean.
06Example 3: longest common subsequence
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])
return dp[-1][-1]
print(lcs("ABCBDAB", "BDCABA")) # 4dp[i][j] is the LCS length of the first i characters of a and the first j of b. If the last characters match, extend the diagonal answer by one. Otherwise take the better of dropping a character from either string. The result 4 corresponds to subsequences such as BCBA. Time and space are O(len(a) x len(b)). This table is the idea behind diff tools and edit distance.
07Example 4: 0/1 knapsack and the loop direction trap
def knap(w, v, W):
dp = [0] * (W + 1)
for wi, vi in zip(w, v):
for c in range(W, wi - 1, -1): # downward
dp[c] = max(dp[c], dp[c - wi] + vi)
return dp[W]
print(knap([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9With weights 1, 3, 4, 5 and values 1, 4, 5, 7 and capacity 7, the best is items of weight 3 and 4 for value 9. The one-dimensional table works because iterating downward ensures dp[c - wi] still holds the value from before the current item was considered. If you iterate upward, an item can be used again and again, which turns it into the unbounded knapsack. For a single item of weight 2 and value 3 with capacity 6, the downward loop gives 3 and the upward loop gives 9. Both loops look alike and answer different questions.
08Common interview questions
Q: How do you know a problem needs DP?
A: It asks for a best value or a count, and the problem splits into smaller versions of itself that repeat.
Q: Memoisation or tabulation?
A: Memoisation is easier to write and only computes needed states. Tabulation avoids recursion depth limits and often allows space optimisation.
Q: DP versus divide and conquer?
A: Divide and conquer splits into independent subproblems, as in merge sort. DP subproblems overlap, so results are cached.
Q: DP versus greedy?
A: Greedy commits to a local choice and needs a proof. DP considers all choices over subproblems. Coins 1, 3, 4 for amount 6 shows greedy failing.
Q: Complexity of coin change?
A: O(amount x number of coins) time and O(amount) space.
Q: How do you reduce the space of a 2D DP?
A: If each row depends only on the previous row, keep two rows, or one with the right loop direction.