Dynamic Programming

Dynamic Programming solves problems by breaking them into overlapping subproblems, solving each once, and storing the result.

Two approaches:
• Top-down (Memoization) → recursion + cache. Natural to write, start here
• Bottom-up (Tabulation) → fill a table iteratively. No recursion overhead, often faster

DP applies when:
1. Optimal substructure → optimal solution contains optimal solutions to subproblems
2. Overlapping subproblems → same subproblems solved multiple times

The DP thinking process:
1. Define dp[i] or dp[i][j] — what does it represent?
2. Find the recurrence relation → how does dp[i] depend on previous states?
3. Set base cases
4. Determine traversal order (which dp values need to be computed first?)

Common DP patterns:
• 1D DP: fibonacci, climbing stairs, house robber
• 2D DP: grid paths, edit distance, LCS
• Knapsack: subset sum, coin change, 0/1 knapsack
• Interval DP: matrix chain, burst balloons

1import functools
2
3# ── Fibonacci — three ways ────────────────────────────────────────
4# 1. Naive recursion: O(2^n)
5def fib_naive(n): return n if n <= 1 else fib_naive(n-1) + fib_naive(n-2)
6
7# 2. Top-down memoization: O(n)
8@functools.cache
9def fib_memo(n): return n if n <= 1 else fib_memo(n-1) + fib_memo(n-2)
10
11# 3. Bottom-up tabulation: O(n) time, O(1) space
12def fib_dp(n):
13    if n <= 1: return n
14    a, b = 0, 1
15    for _ in range(2, n+1): a, b = b, a + b
16    return b
17
18# ── Climbing Stairs ───────────────────────────────────────────────
19def climb_stairs(n: int) -> int:
20    if n <= 2: return n
21    a, b = 1, 2
22    for _ in range(3, n+1): a, b = b, a + b
23    return b
24
25# ── House Robber ─────────────────────────────────────────────────
26def rob(nums: list[int]) -> int:
27    prev2 = prev1 = 0
28    for num in nums:
29        prev2, prev1 = prev1, max(prev1, prev2 + num)
30    return prev1
31
32# ── Coin Change (bottom-up) ───────────────────────────────────────
33def coin_change(coins: list[int], amount: int) -> int:
34    dp = [float('inf')] * (amount + 1)
35    dp[0] = 0
36    for coin in coins:
37        for x in range(coin, amount + 1):
38            dp[x] = min(dp[x], dp[x - coin] + 1)
39    return dp[amount] if dp[amount] != float('inf') else -1
40
41# ── Longest Common Subsequence (2D DP) ───────────────────────────
42def lcs(text1: str, text2: str) -> int:
43    m, n  = len(text1), len(text2)
44    dp    = [[0] * (n+1) for _ in range(m+1)]
45    for i in range(1, m+1):
46        for j in range(1, n+1):
47            if text1[i-1] == text2[j-1]:
48                dp[i][j] = dp[i-1][j-1] + 1
49            else:
50                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
51    return dp[m][n]
52
53# ── 0/1 Knapsack ─────────────────────────────────────────────────
54def knapsack(weights, values, capacity):
55    n  = len(weights)
56    dp = [[0] * (capacity+1) for _ in range(n+1)]
57    for i in range(1, n+1):
58        for w in range(capacity+1):
59            dp[i][w] = dp[i-1][w]
60            if weights[i-1] <= w:
61                dp[i][w] = max(dp[i][w], values[i-1] + dp[i-1][w-weights[i-1]])
62    return dp[n][capacity]
63
64print(fib_dp(10))                              # 55
65print(climb_stairs(5))                         # 8
66print(rob([2,7,9,3,1]))                        # 12
67print(coin_change([1,3,4], 6))                 # 2
68print(lcs("abcde", "ace"))                     # 3
69print(knapsack([1,3,4,5], [1,4,5,7], 7))       # 9