11. Dynamic Programming

What Interviewers Test Here

• Identifying overlapping subproblems (the key signal for DP)
• Top-down: add @cache to a natural recursion
• Bottom-up: translate recursion into a table
• Common patterns: knapsack, LIS, LCS, coin change, grid paths

---

The DP Development Process

1. Define state: dp[i] means "answer for subproblem with parameter i"
2. Write recurrence: how does dp[i] relate to dp[i-1], dp[i-2], etc?
3. Identify base cases: smallest valid input with known answer
4. Decide direction: top-down (@cache) or bottom-up (table)
5. Optimise space: often a 1D table suffices instead of 2D

from functools import cache

# --- House Robber ---
def rob(houses: list[int]) -> int:
    # dp[i] = max money from houses[0..i]
    # dp[i] = max(dp[i-1], dp[i-2] + houses[i])
    prev2 = prev1 = 0
    for h in houses:
        prev2, prev1 = prev1, max(prev1, prev2 + h)
    return prev1

# --- 0/1 Knapsack ---
def knapsack(wt: list[int], val: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):   # backwards!
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

# --- Longest Common Subsequence ---
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]

---

Conceptual Q&A

Q1: "How do you know a problem requires dynamic programming?"

Walkthrough:

"Two signals:

1. Optimal substructure: the optimal solution to the problem can be built from optimal solutions to sub-problems. (e.g., shortest path from A to C through B = shortest A→B + shortest B→C)
2. Overlapping subproblems: the same sub-problem is computed multiple times in a naive recursive solution.

Question types that often signal DP:

• 'Minimum/maximum cost to...'
• 'Number of ways to...'
• 'Can you achieve X?'
• 'Longest/shortest subsequence/path...'

My process: write the brute force recursion first. If I see the same function call with the same arguments more than once, that's the DP signal — cache it."

---

Q2: "Climbing stairs: you can take 1 or 2 steps. How many ways to reach step n?"

Walkthrough:

"This is a classic DP problem. Let me think recursively: to reach step n, I came from either step n-1 (took 1 step) or step n-2 (took 2 steps). So ways(n) = ways(n-1) + ways(n-2).

Base cases: ways(0) = 1 (one way to stay at ground), ways(1) = 1 (one way to reach step 1).

This is exactly Fibonacci! I can solve it in $O(n)$ time and $O(1)$ space."

def climb_stairs(n: int) -> int:
    if n <= 1: return 1
    a, b = 1, 1   # ways(0), ways(1)
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Or with memoization (shows the thought process clearly)
@cache
def climb_stairs_memo(n: int) -> int:
    if n <= 1: return 1
    return climb_stairs_memo(n-1) + climb_stairs_memo(n-2)

---

Q3: "Minimum cost to reach the last cell of a grid (can only move right or down)."

Walkthrough:

"To reach cell (i, j), I came from (i-1, j) (above) or (i, j-1) (left). I want the minimum cost path.

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Base cases: first row (can only come from left), first column (can only come from above).

This is bottom-up tabulation. $O(m \times n)$ time and space."

def min_path_cost(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]

    for j in range(1, n):              # first row — can only come from left
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):              # first col — can only come from above
        dp[i][0] = dp[i-1][0] + grid[i][0]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

    return dp[m-1][n-1]

---