Dynamic programming (DP) solves problems by breaking them into overlapping subproblems, solving each once, and storing the results. Two approaches:
Top-down (memoisation): recursive, cache results in a dict.
Bottom-up (tabulation): iterative, fill a table from base cases up.
DP is applicable when a problem has optimal substructure (optimal solution uses optimal solutions to subproblems) and overlapping subproblems (same subproblems solved repeatedly).
Fibonacci — Memoisation vs Tabulation
# Naive recursion: O(2^n) — recomputes same valuesdeffib_naive(n): return n if n <= 1elsefib_naive(n-1) + fib_naive(n-2)
# Memoisation: O(n) time, O(n) spacefrom functools import lru_cache
@lru_cache(maxsize=None)
deffib(n): return n if n <= 1elsefib(n-1) + fib(n-2)
# Tabulation: O(n) time, O(1) space (rolling)deffib_tab(n):
a, b = 0, 1for _ inrange(n): a, b = b, a + b
return a
0/1 Knapsack
Given n items with weights and values, and a bag of capacity W: maximise total value without exceeding W. Each item can be taken at most once.
defknapsack(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ inrange(n+1)]
for i inrange(1, n+1):
for w inrange(W+1):
dp[i][w] = dp[i-1][w] # skip itemif weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w-weights[i-1]] + values[i-1]) # take itemreturn dp[n][W] # O(nW) time and space
Longest Common Subsequence (LCS)
Classic DP: find the longest subsequence common to two strings.
deflcs(s, t):
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ inrange(m+1)]
for i inrange(1, m+1):
for j inrange(1, n+1):
if s[i-1]==t[j-1]: dp[i][j] = dp[i-1][j-1] + 1else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n] # O(mn)print(lcs("ABCBDAB", "BDCAB")) # 4 (BCAB)
Practice
1. What are the two necessary conditions for DP to apply?
1. Optimal substructure: an optimal solution to the problem
contains optimal solutions to its subproblems.
2. Overlapping subproblems: the same subproblems are solved
multiple times in a naive recursive approach.
If both hold, DP avoids redundant work and reduces exponential to polynomial.
2. Solve: minimum coin change. Given coins=[1,5,10,25] and amount=36, find the fewest coins.
def min_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] # min_coins([1,5,10,25], 36) = 3 (25+10+1)
Knowledge Check
Dynamic programming differs from plain recursion by
DP can be either recursive (memoisation) or iterative (tabulation).
Correct — memoisation/tabulation caches results; each subproblem is solved once.
DP solves graph, string, and 2D grid problems too.
DP complexity depends on the number of subproblems; it's O(nW) for knapsack, O(mn) for LCS.
Recap: DP = recursion + caching. Without caching, fib(50) calls fib(2) over a trillion times. With memoisation, fib(2) is computed once.
The time complexity of naive recursive Fibonacci is
That's the memoised version.
Correct — each call makes two more calls; tree of calls has 2^n nodes.
No divide-and-conquer halving here.
The call tree doubles, not squares.
Recap: fib(n) calls fib(n-1) + fib(n-2). Call tree has ~2^n nodes total. Memoisation reduces to O(n) — each fib(k) computed exactly once.
Tabulation (bottom-up DP) differs from memoisation (top-down) in that
Asymptotically equivalent; tabulation avoids recursion overhead in practice.
Correct — tabulation = no recursion, fill table; memoisation = recurse, cache on the way back.
Both approaches work for 2D problems like LCS and knapsack.
They typically use similar amounts of memory.
Recap: both solve each subproblem once. Tabulation avoids call stack overhead. Memoisation is easier to write (follows the recursive structure). Choose based on context.
The 0/1 knapsack problem is called '0/1' because
Values can be any positive integers.
Correct — unlike fractional knapsack, you can't take a partial item.
That's not a valid complexity.
Items have arbitrary weights and values.
Recap: 0/1 = binary choice per item. Fractional knapsack (take portions) is solved greedily in O(n log n). 0/1 knapsack requires DP: O(nW).
LCS of 'ABCD' and 'ACBD' is
Multiple characters match.
Correct — one LCS is 'ACD' (or 'ABD'); length 3.
Not all 4 characters appear as a common subsequence in order.
Longer common subsequences exist.
Recap: LCS('ABCD','ACBD'): dp table gives length 3. Example LCS: A-C-D (positions 0,2,3 in first; 0,1,3 in second).