12. Dynamic Programming

Key Insight

DP = recursion + memoization = identifying overlapping subproblems in a search space and caching results. Always define the state (what parameters uniquely determine a subproblem) and the transition (how a state is computed from smaller states). Then choose top-down (memoization) or bottom-up (tabulation).

---

12.1 Top-Down vs Bottom-Up

from functools import cache, lru_cache

# Top-down: natural recursion + @cache (Python 3.9+)
@cache
def fib(n: int) -> int:
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Bottom-up: explicit table, better space control
def fib_dp(n: int) -> int:
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

---

12.2 Pattern 1 — 0/1 Knapsack

State: dp[i][w] = max value using first i items with capacity w.
Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])

def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [0] * (W + 1)          # space-optimised 1D
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):   # iterate backwards!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# Unbounded knapsack (item reuse allowed)
def knapsack_unbounded(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for w in range(1, W + 1):   # iterate forwards (allow reuse)
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

---

12.3 Pattern 2 — Longest Increasing Subsequence (LIS)

# O(n²) DP
def lis_n2(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(n log n) — patience sorting
import bisect
def lis_nlogn(nums: list[int]) -> int:
    tails = []   # tails[i] = smallest tail of all increasing subseqs of length i+1
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

---

12.4 Pattern 3 — Longest Common Subsequence (LCS)

def lcs(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == t[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[m][n]

# Edit distance (Levenshtein)
def edit_distance(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        prev = dp[:]
        dp[0] = i
        for j in range(1, n + 1):
            if s[i-1] == t[j-1]:
                dp[j] = prev[j-1]
            else:
                dp[j] = 1 + min(prev[j], dp[j-1], prev[j-1])
    return dp[n]

---

12.5 Pattern 4 — Coin Change

# Minimum coins (unbounded)
def coin_change(coins: list[int], amount: int) -> int:
    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] if dp[amount] != float("inf") else -1

# Number of ways (unbounded)
def coin_change_ways(coins: list[int], amount: int) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:              # iterate coins outer to avoid order counting
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

---

12.6 Pattern 5 — Interval DP

State: dp[i][j] = answer for subarray/interval [i..j].
Key: always iterate by length in the outer loop.

# Matrix chain multiplication
def matrix_chain(dims: list[int]) -> int:
    n = len(dims) - 1   # number of matrices
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

# Burst balloons
def max_coins(nums: list[int]) -> int:
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
                )
    return dp[0][n-1]

# Palindrome partitioning (min cuts)
def min_cut(s: str) -> int:
    n = len(s)
    # Precompute palindrome table
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = (s[i]==s[j]) and (j-i <= 2 or is_pal[i+1][j-1])
    dp = list(range(n))   # dp[i] = min cuts for s[0..i]
    for i in range(1, n):
        if is_pal[0][i]:
            dp[i] = 0
        else:
            for j in range(1, i+1):
                if is_pal[j][i]:
                    dp[i] = min(dp[i], dp[j-1] + 1)
    return dp[n-1]

---

12.7 Pattern 6 — State Machine DP

Use when: problem has discrete modes/states (buy/sell/hold, locked/unlocked).

# Best time to buy and sell stock with cooldown
def stock_with_cooldown(prices: list[int]) -> int:
    hold = float("-inf")  # max profit while holding a stock
    sold = 0              # max profit just sold (in cooldown)
    rest = 0              # max profit in rest state
    for p in prices:
        prev_sold = sold
        sold = hold + p
        hold = max(hold, rest - p)
        rest = max(rest, prev_sold)
    return max(sold, rest)

# Buy/sell with transaction fee
def stock_with_fee(prices: list[int], fee: int) -> int:
    hold = -prices[0]
    cash = 0
    for p in prices[1:]:
        hold = max(hold, cash - p)
        cash = max(cash, hold + p - fee)
    return cash

# At most k transactions
def stock_k_transactions(k: int, prices: list[int]) -> int:
    n = len(prices)
    if k >= n // 2:  # unlimited transactions
        return sum(max(0, prices[i+1]-prices[i]) for i in range(n-1))
    dp = [[0]*n for _ in range(k+1)]
    for t in range(1, k+1):
        max_so_far = -prices[0]
        for d in range(1, n):
            dp[t][d] = max(dp[t][d-1], prices[d] + max_so_far)
            max_so_far = max(max_so_far, dp[t-1][d] - prices[d])
    return dp[k][n-1]

---

12.8 Key CP Patterns

Pattern	State definition	Transition trigger
0/1 Knapsack	dp[i][w] — items, capacity	Include/exclude item
LIS	dp[i] — length ending at i	Extend smaller element
LCS / Edit	dp[i][j] — prefixes of two strings	Match or mismatch
Coin change	dp[amount]	Try each coin
Interval DP	dp[i][j] — subarray	Try each split point k
State machine	One var per state	Price event / day
Bitmask DP	dp[mask] — subset visited	Add next unvisited node

---