12. Dynamic Programming

What Is Dynamic Programming?

Dynamic Programming (DP) is an optimisation technique for recursive problems where the same sub-problems are solved repeatedly. The solution: compute each sub-problem once and store the result.

Two approaches:

1. Top-down (memoization): Write the natural recursion, then cache results using a dict or @cache.
2. Bottom-up (tabulation): Fill a table iteratively, building from small sub-problems to large.

When to use DP: When you see "optimal value" (minimum/maximum), "number of ways", or "can you achieve X?" — and the problem has overlapping sub-problems.

---

12.1 Memoization

from functools import cache

# --- Fibonacci (inefficient without cache) ---
# fib(40) makes billions of recursive calls without memoization
@cache
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)   # each value computed ONCE, then cached

print(fib(100))  # instant — 354224848179261915075

# --- Climbing stairs (1 or 2 steps at a time) ---
# How many distinct ways to reach step n?
@cache
def climb(n: int) -> int:
    if n <= 1: return 1
    if n == 2: return 2
    return climb(n - 1) + climb(n - 2)   # same structure as Fibonacci!

print(climb(10))  # 89

---

12.2 Bottom-Up Tabulation

# --- Fibonacci — bottom-up (O(n) time, O(1) space) ---
def fib_table(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

# --- Coin Change (minimum coins to make amount) ---
# coins = [1, 5, 10, 25], amount = 36 → answer = 3 (25+10+1)
def coin_change(coins: list[int], amount: int) -> int:
    # dp[a] = minimum coins needed to make amount a
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0   # base case: 0 coins needed for amount 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float("inf") else -1

print(coin_change([1, 5, 10, 25], 36))  # 3

# --- Longest Common Subsequence (LCS) ---
# LCS("abcde", "ace") = 3 ("ace")
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]

print(lcs("abcde", "ace"))   # 3

---

12.3 Common DP Patterns

# --- 0/1 Knapsack (include/exclude each item) ---
# n items, each with weight and value, knapsack capacity W
# Maximise total value without exceeding capacity
def knapsack(weights: list[int], values: list[int], W: int) -> int:
    n   = len(weights)
    dp  = [0] * (W + 1)
    for i in range(n):
        # Iterate backwards to avoid using item i twice
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# --- Longest Increasing Subsequence (LIS) ---
# Find the length of the longest strictly increasing subsequence
def lis(nums: list[int]) -> int:
    if not nums: return 0
    dp = [1] * len(nums)   # every element is a subsequence of length 1
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 (2,3,7,101 or 2,5,7,101)

# --- House Robber (no two adjacent houses) ---
# Max money you can rob without robbing adjacent houses
def rob(houses: list[int]) -> int:
    prev2 = prev1 = 0
    for amount in houses:
        prev2, prev1 = prev1, max(prev1, prev2 + amount)
    return prev1

print(rob([2, 7, 9, 3, 1]))  # 12 (2+9+1)

---