Chapter 13: Dynamic Programming

Vol 2: Algorithm Forest Adventure · Station 13

---

Metadata Card

Attribute	Value
Difficulty	(Nightmare start)
Prerequisites	Recursion, Backtracking, Hash Tables
Core Idea	Remember the past, reuse the future
Keywords	Memoization Tabulation DP Table 0-1 Knapsack LCS LIS State Transition

---

Your Progress

You've discovered that some problems, when broken down, produce identical subproblems. Your old approach was to recompute them. Too foolish. Master Chen's letter reads: "Some answers — just remember them. Next time, use your memory."

---

Breakthrough · Origins

Fibonacci: From O(2ⁿ) to O(n)

# Naive: O(2ⁿ)
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

# Memoization (top-down): O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

# Tabulation (bottom-up): O(n), O(1) space
def fib_tab(n):
    if n <= 1: return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

DP Three Elements

1. Overlapping Subproblems: Same subproblems appear multiple times
2. Optimal Substructure: Optimal solution contains optimal sub-solutions
3. State Transition Equation: How to derive current state from previous states

Classic 1D DP: House Robber

def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

Classic 2D DP: Unique Paths

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

0-1 Knapsack

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

Why reverse iteration? Each item can only be used once. Reverse ensures dp[w - weights[i]] reads the previous row's value.

LCS (Longest Common Subsequence)

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[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]

LIS (Longest Increasing Subsequence)

def length_of_lis(nums):
    if not nums: return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

---

Verification Checklist

• [ ] Can explain DP three elements with examples
• [ ] Can implement Fibonacci (memo + tab)
• [ ] Can implement 0-1 knapsack (2D → 1D, why reverse)
• [ ] Can implement LCS and LIS
• [ ] Can distinguish DP from Divide & Conquer (overlapping subproblems)

---

Traveler's Notes

• DP isn't an algorithm — it's a way of thinking: from "how to compute" to "how to remember"
• First write brute-force recursion, then identify repeated parameters
• Add a dummy row/column to your DP table to handle boundaries
• All sequence DP problems share the same structure: at step i, make a choice based on previous states

---

→ Next Stop Preview

Chapter 14: Greedy Algorithms — "Local optimum → global optimum? Don't trust it too soon."