第13章：动态规划

元数据卡

字段	值
难度等级	（噩梦开局）
前置章节	第9章递归与回溯、第10章哈希表
核心思想	记住过去，复用未来
实战出镜率	面试高频 × 工程中频
读本章姿势	纸上画图 → 写代码验证 → 去 LeetCode 刷到吐

你在哪

你发现有些问题拆了再拆，拆出来的小问题和前面的完全一样。你之前的方案是重新算一遍。太傻。老陈的信里最后一句："有些答案，记住它就好。下次用回记忆。"——动态规划。

你已经读完了递归与回溯，会用分治把大问题拆成小问题。但有个事一直让你不爽：斐波那契递归写出来，n=40 就卡得要死，n=100 直接爆炸。 回调栈里相同参数重复算了上千遍，而你却眼睁睁看着。

这是 Vol 2 第一个真正意义上的 "怎么让计算机变聪明" 的章节。前面的章节是教计算机认识数据、排列数据、搜索数据；从这章开始，你要教计算机 做决策。

你的任务

本章分层
必读（DP 入门）：重叠子问题与记忆化（Fibonacci 级别）；DP 三要素；选 2-3 个经典模型——爬楼梯（一维 DP）、网格路径 / 最小路径和（二维 DP）、0-1 背包（选做）
DP 进阶（选读）：0-1 背包的完全背包变体；最长公共子序列（LCS）；最长递增子序列（LIS）的 O(n²) 版
专题深入：区间 DP（最长回文子序列）；状态压缩 DP（TSP）；O(n log n) 的 LIS
本章不会要求你掌握
状态压缩 DP 的完整实现（了解概念即可）
区间 DP（矩阵链乘等）
LIS 的 O(n log n) 贪心+二分优化

驿站长老扔给你一张泛黄的羊皮纸，上面列了三类问题：

"给一袋森林物资，每种物资有不同重量，怎么组合能凑出目标重量，且用的件数最少？"
"从森林东边的瞭望台走到西边的水源地，一共有几条不同的兽道路径？"
"两条不同的林间日志，最长共同记录了什么内容？"

随便哪个，暴力解都能跑到宇宙热寂。你要做的是：学会一套通用框架，把所有这类问题从指数时间砸到多项式时间。

遭遇战 → 获得技能

情景：石碑上的斐波那契谜题

你在林间空地发现一块石碑，上面刻着一道古老的谜题。前人的笔记在旁边写着：

python

# 第一版——看起来对，但跑得奇慢
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# n = 50 → 你等了很久，石碑纹丝不动

你翻开笔记，发现后面有一段话："能不能优化一下？"

python

# 加入记忆化（Memoization）—— 这回对了
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)

# n = 100 → 几乎是瞬出，递归深度依然是问题

这就是你遇到的第一个动态规划问题。 而你甚至还没意识到。

💡 技能获得：重叠子问题识别

原始 Fibonacci	参数调用次数
朴素递归	`fib(30)` 被重复算了 8,328,040 次
加缓存	每个 n 只算 1 次，总共算 50 次

mermaid

flowchart TD
    fib5["fib(5)"]
    fib4["fib(4)"]
    fib3["fib(3)"]
    fib3b["fib(3)"]
    fib2["fib(2)"]
    fib2b["fib(2)"]
    fib2c["fib(2)"]
    fib1["fib(1)"]
    fib1b["fib(1)"]
    fib1c["fib(1)"]
    fib1d["fib(1)"]
    fib0["fib(0)"]
    fib0b["fib(0)"]
    fib0c["fib(0)"]

    fib5 --> fib4
    fib5 --> fib3

    fib4 --> fib3b
    fib4 --> fib2

    fib3 --> fib2b
    fib3 --> fib1

    fib3b --> fib2c
    fib3b --> fib1b

    fib2 --> fib1c
    fib2 --> fib0

    fib2b --> fib1d
    fib2b --> fib0b

    fib2c --> fib1b
    fib2c --> fib0c

    style fib3 fill:#ff9999,stroke:#333
    style fib3b fill:#ff9999,stroke:#333
    style fib2 fill:#99ff99,stroke:#333
    style fib2b fill:#99ff99,stroke:#333
    style fib2c fill:#99ff99,stroke:#333
    style fib1 fill:#9999ff,stroke:#333
    style fib1b fill:#9999ff,stroke:#333
    style fib1c fill:#9999ff,stroke:#333
    style fib1d fill:#9999ff,stroke:#333

标注的节点：粉色 = fib(3) 出现了两次，绿色 = fib(2) 出现三次，蓝色 = fib(1) 出现四次。这些重复计算的子树就是重叠子问题——DP 用缓存或表格把它们变成只算一次。

画个递归树，找找哪些子树是完全一样的——找到的那一瞬间，你就能用 DP 了。

常见陷阱

1. DP 三要素——面试官的灵魂拷问

面试官："你说你会 DP，那你说说 DP 的三个要素是什么？"

这三个概念是入门的门槛，但很多工程师背了三年都没真正理解。

1.1 重叠子问题（Overlapping Subproblems）

想象你要准备一次林间篝火野炊。你要算 "从下午 2 点到 6 点，能不能完成 12 道食物"。

如果你用分治的思路：把 12 份食物拆成 A 做 6 份 + B 做 6 份，各自再拆。但如果 A 和 B 都要用到唯一的火堆，你拆出来的子问题就不是独立的——它们重叠了。

判断标准： 把递归树画出来，看有没有相同的子树出现多次。有 → DP 候选；没有 → 多半是分治。

1.2 最优子结构（Optimal Substructure）

"大问题的最优解，包含子问题的最优解。"

🌰 经典例子——你从森林东岸营地到西岸驿站的最短路径经过山腰的水源，那么从东岸营地到水源的那段，一定也是东岸营地到水源的最短路径。否则你可以换一条更短的，整体就更短了。

陷阱： 很多问题看起来有最优子结构，实际没有。比如无权图中的最长简单路径——最长路径的子路径不一定是子问题的最长路径。

1.3 状态转移方程（State Transition）

这是 DP 的灵魂，也是大部分人觉得难的地方。

状态转移方程就是：告诉我前一步的状态，我就能推出当前步的状态。

python

# 斐波那契的状态转移
# dp[n] = dp[n-1] + dp[n-2]
# 边界：dp[0] = 0, dp[1] = 1

# 爬楼梯的 DP——状态转移：到第 i 阶 = 从 i-1 阶跨一步 + 从 i-2 阶跨两步
def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

状态 = 参数空间。转移 = 怎么从旧参数算新参数。

2. Memoization vs Tabulation

维度	Memoization（记忆化递归）	Tabulation（表格迭代）
方向	自顶向下（Top-down）	自底向上（Bottom-up）
实现	递归 + 缓存	循环 + 数组
优点	只算需要的状态，直觉自然	无递归栈溢出，性能可控
缺点	递归深度限制，有额外调用开销	可能算不需要的状态
复杂度	O(状态数 × 转移代价)	同上
典型场景	树形 DP、区间 DP	背包、序列 DP

python

# ① Memoization —— 自顶向下，递归 + 缓存
def fib_top_down(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_top_down(n - 1, memo) + fib_top_down(n - 2, memo)
    return memo[n]

# ② Tabulation —— 自底向上，循环迭代
def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

java

// Java: 自底向上
public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}
// 输出: fib(50) = 12586269025

cpp

// C++: 空间优化（滚动数组）
int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
// 输出: fib(100) = 354224848179261915075（需用 64-bit）

工程经验： 面试用 Memoization 快速写出原型，然后说"我们可以优化为 Bottom-up 省掉递归开销"。这就是展现工程思维的套路。实际项目里——谁敢用递归算大 n？老老实实迭代。

3. 经典序列问题

这一节用一个递进式案例串起来，你会发现它们本质是一个模子的变体。

3.1 打家劫舍（House Robber）

问题： 一溜房子排成排，每个房子有金额。你不能偷相邻的两家，问最多能偷多少。

状态定义： dp[i] = 偷前 i 个房子能获得的最大金额。

转移方程： 到第 i 个房子时，两个选择：

不偷：dp[i] = dp[i-1]
偷：dp[i] = dp[i-2] + nums[i]（因为不能偷 i-1）
取 max

python

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]

# 测试
print(rob([2, 7, 9, 3, 1]))  # 输出: 12 (偷 2+9+1)

你注意到了吗？打家劫舍的 DP 和斐波那契结构一模一样，只是从加法换成了取 max。

💡 启示： 所有序列 DP 问题的本质都一样——到第 i 步时，基于前几步的状态，做一次选择。

3.2 三种经典序列 DP 对比

问题	状态定义	转移方程	空间优化
斐波那契	`dp[i]` = 第 i 个数	`dp[i]=dp[i-1]+dp[i-2]`	滚动到 2 个变量
爬楼梯	`dp[i]` = 到 i 阶的方法数	`dp[i]=dp[i-1]+dp[i-2]`	同上
打家劫舍	`dp[i]` = 前 i 间偷到的 max	`dp[i]=max(dp[i-1],dp[i-2]+nums[i])`	滚动到 2 个变量

它们三个的状态转移方程高度相似，区别只在聚合函数和边界条件。 这就是为什么 DP 入门从这三道题开始。

4. 路径问题——二维 DP 的经典范本

4.1 网格路径（Unique Paths）

一个 m×n 的网格，从左上角走到右下角，每次只能向右或向下走，有多少条不同路径？

python

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    # 第一行和第一列都只有 1 种走法（一直向右或一直向下）
    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]

print(unique_paths(3, 7))  # 输出: 28

状态转移图：

  (i-1, j)
      ↓
(i, j-1) → (i, j)

💡 模式识别： 二维 DP 的核心是明确遍历顺序。必须先处理第一行和第一列（基线条件），然后按行或按列填充。

4.2 最小路径和（Min Path Sum）

每个格子有正数，找一条从左上到右下路径，路径上的数字之和最小。

python

def min_path_sum(grid):
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    # 填第一列
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    # 填第一行
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    # 填剩余格子
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    return dp[m - 1][n - 1]

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print(min_path_sum(grid))  # 输出: 7 (1→3→1→1→1)

** 常见坑：** 有人直接在原数组上修改省空间，生产环境别这么干——副作用会咬你。要么用 1D 滚动数组，要么声明一个新的 dp。

5. 0-1 背包——DP 入门的试金石

问题： 有 N 个物品，每个物品有重量 w[i] 和价值 v[i]。你的背包容量为 W。每个物品只能拿 0 个或 1 个，问能装的最大总价值。

python

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i - 1][w],                      # 不拿
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  # 拿
                )
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_01(weights, values, 8))  # 输出: 10 (物品 3+4: 5+5 或 2+5: 3+6)

二维→一维的妙手：

python

def knapsack_01_optimized(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):  # 反向遍历！
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

为什么反向遍历？ —— 为了确保每个物品只被使用一次。反向时 dp[w - weights[i]] 读到的还是上一轮的值（没拿当前物品）；如果是正向遍历，同一物品会被多次"偷"着用。

完全背包则恰恰相反——正向遍历，因为每个物品可以无限取：

python

def knapsack_unbounded(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(weights[i], W + 1):  # 正向遍历！
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

💡 口诀： 0-1 背包反向遍历，完全背包正向遍历。背住它，写到简历上。

6. 双序列 DP

6.1 最长公共子序列（Longest Common Subsequence, LCS）

给定两个字符串 text1 和 text2，返回它们的最长公共子序列长度。子序列不要求连续，但顺序必须一致。

状态定义： dp[i][j] = text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度。

转移：

如果 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

python

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]

print(longest_common_subsequence("abcde", "ace"))  # 输出: 3 ("ace")

java

// Java: LCS
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}
// "abcde" vs "ace" → 3

cpp

// C++: LCS
int lcs(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (s1[i-1] == s2[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];
}

6.2 最长递增子序列（Longest Increasing Subsequence, LIS）

给定一个无序数组，找最长严格递增的子序列长度。

两种解法对比：

方法	时间复杂度	空间复杂度	原理
DP（经典）	O(n²)	O(n)	`dp[i] = max(dp[j]+1)`
贪心+二分（优化，选读）	O(n log n)	O(n)	维护 tails 数组——属于进阶

python

# O(n²) DP —— 面试够用
def length_of_lis_dp(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)

# O(n log n) 贪心+二分 —— 面试加分
import bisect
def length_of_lis_fast(nums):
    tails = []
    for num in nums:
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num
    return len(tails)

print(length_of_lis_dp([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出: 4 ([2,3,7,101])

** 常见卡点：** bisect_left 和 bisect_right 的区别。LIS 要求严格递增（不能相等），所以用 bisect_left 替换 >= num 的元素；如果允许相等，用 bisect_right。

专题深入：区间 DP

区间 DP 是 DP 的进阶专题。 主线先掌握爬楼梯/路径/背包等经典模型即可，区间 DP 在需要时再回来看。

模式识别： 问题涉及 "某个区间 [i, j] 上的最优解"，且大区间依赖小区间。

经典问题是矩阵链乘和回文子串分割。

python

# 最长回文子序列（Longest Palindromic Subsequence）
def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1  # 单个字符是回文
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

print(longest_palindrome_subseq("bbbab"))  # 输出: 4 ("bbbb")

区间 DP 的遍历顺序很有讲究：i 从大到小，j 从小到大。为什么要这样？因为 dp[i][j] 依赖 dp[i+1][j-1]（左下角）、dp[i+1][j]（下边）、dp[i][j-1]（左边）——所以填充方向必须从下往上、从左到右。

    j →
i   [i,j] 依赖 dp[i+1][j-1], dp[i+1][j], dp[i][j-1]
↓   所以 i 从大往小，j 从小往大

专题深入：状态压缩 DP——TSP 入门

状态压缩 DP 属于高级专题，初次学习时可跳过。 知道"可以用二进制位表示集合状态"就够了。

旅行商问题（Traveling Salesman Problem, TSP）： 一个商人要访问 n 个城市，每个城市恰好访问一次，最后回到起点。找最短路径。

这是 NP-hard 问题，但用状态压缩 DP 可以把 O(n!) 降到 O(n²·2ⁿ) —— n=20 时已经从天文数字降到了勉强可行。

核心思想： 用二进制位表示"哪些城市已经访问过"。

python

# TSP 状态压缩 DP（简化版，假设城市 0 为起点）
def tsp(mask, pos, dist, n, memo):
    if mask == (1 << n) - 1:  # 所有城市都访问了
        return dist[pos][0]    # 返回起点
    if (mask, pos) in memo:
        return memo[(mask, pos)]
    ans = float('inf')
    for city in range(n):
        if not (mask & (1 << city)):  # 还没访问这个城市
            new_dist = dist[pos][city] + tsp(mask | (1 << city), city, dist, n, memo)
            ans = min(ans, new_dist)
    memo[(mask, pos)] = ans
    return ans

# 使用示例
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
n = 4
print(tsp(1, 0, dist, n, {}))  # 输出: 80 (0→1→3→2→0 = 10+25+30+15)

💡 为什么叫"状态压缩"？ 平常 DP 状态是用数组索引表示 visited，状态空间是 n! 种排列。二进制掩码把"哪些城市去过"压缩成一个整数，让你可以用 DP 做递推。

工程现实： TSP 状态压缩 DP 在 n > 20 时也会内存爆炸（2²⁰ × 20 ≈ 20M 状态）。真正生产环境用启发式（模拟退火、遗传算法）或精确求解器（Concorde）。

通关挑战

挑战 1：零钱兑换（Coin Change）

给定不同面额的 coins 和一个总金额 amount，求凑成 amount 所需的最少硬币数。如果不可能，返回 -1。

python

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 2, 5], 11))  # 输出: 3 (5+5+1)
print(coin_change([2], 3))         # 输出: -1

挑战 2：编辑距离（Edit Distance）

两个单词 word1 和 word2，每次可以插入、删除、替换一个字符。求最少操作次数。

python

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1]   # 替换
                )
    return dp[m][n]

print(min_distance("horse", "ros"))  # 输出: 3

验收标准

学了这章，你要能回答以下问题——答不上来就回去再看：

DP 三要素是哪三个？举一个反面例子（有重叠子问题但无最优子结构）。
写一段代码：给 [2, 7, 9, 3, 1] 求打家劫舍最大金额，并画 DP 表。
0-1 背包的 2D DP 如何优化到 1D？为什么反向遍历？
LCS 和 LIS 的状态定义和转移方程各是什么？
区间 DP 的遍历顺序为什么是 i 从大到小、j 从小到大？
状态压缩 DP 中 mask 是什么含义？写一个迭代版 TSP。

常见卡点

卡点	症状	怎么办
状态定义不清楚	写了半天不知道 dp[i][j] 代表啥	先写人话："dp[i][j] = 前 i 个物品在容量 j 下..."
边界搞错	dp[0] 或 dp[-1] 索引越界	加上守卫（dummy 行/列），让索引对齐语义
转移顺序反了	结果永远是 0	画一个二维矩阵，标出 dp[i][j] 依赖哪些格子
二维→一维改错	完全背包和 0-1 背包混了	牢记：0-1 反向，完全正向
DP 维度太多	三维 DP 脑子转不过弯	按 C++ 声明 `dp[a][b][c]` 的方式，逐维确定范围

现在不需要理解

DP 的数学证明（Bellman 方程、最优性原理）——工程中使用不依赖严格证明
斜率优化（Convex Hull Trick）——面试不考，竞赛内容
DP 对偶（费用流转 DP） ——极少用到
树形 DP 的换根法——超过 99% 的面试难度

旅人笔记

2017 年我第一次刷 DP，看着打家劫舍的题解楞了半小时。第二天懂了斐波那契之后，突然发现爬楼梯、打家劫舍、零钱兑换都是同一个套路。那时候我才明白：DP 不是一种算法，是一种思维转换——从"怎么算"到"怎么记住"。
两个技巧让我的 DP 再也不卡壳：
先写暴力递归，再找重复参数
把数组多加 1 个，用 dummy 行/列处理边界
如果这章你读得满头问号——正常。DP 是所有算法章节里最反直觉的，但它也是最有回报的。去 LeetCode 找"Dynamic Programming"标签，从 Easy 刷到 Medium，大概 30 道题后你就会发现：天下的 DP 都长一个样。
——一个曾经被 DP 血虐的工程师

下一站预告

[第14章：贪心算法] → "如果 DP 是每一步都算一遍所有可能性，贪心就是每一步只选当前看起来最优的——简单、粗暴、经常对。但有时候错得离谱。下一章讲了：当你发现 DP 太慢，而问题又刚好有贪心选择性质——你就找到了比 DP 快一百倍的解法。"

第13章：动态规划 ​

元数据卡 ​

你在哪 ​

你的任务 ​

遭遇战 → 获得技能 ​

情景：石碑上的斐波那契谜题 ​

常见陷阱 ​

1. DP 三要素——面试官的灵魂拷问 ​

1.1 重叠子问题（Overlapping Subproblems） ​

1.2 最优子结构（Optimal Substructure） ​

1.3 状态转移方程（State Transition） ​

2. Memoization vs Tabulation ​

3. 经典序列问题 ​

3.1 打家劫舍（House Robber） ​

3.2 三种经典序列 DP 对比 ​

4. 路径问题——二维 DP 的经典范本 ​

4.1 网格路径（Unique Paths） ​

4.2 最小路径和（Min Path Sum） ​

5. 0-1 背包——DP 入门的试金石 ​

6. 双序列 DP ​

6.1 最长公共子序列（Longest Common Subsequence, LCS） ​

6.2 最长递增子序列（Longest Increasing Subsequence, LIS） ​

专题深入：区间 DP ​

专题深入：状态压缩 DP——TSP 入门 ​

通关挑战 ​

挑战 1：零钱兑换（Coin Change） ​

挑战 2：编辑距离（Edit Distance） ​

验收标准 ​

常见卡点 ​

现在不需要理解 ​

旅人笔记 ​

下一站预告 ​

第13章：动态规划

元数据卡

你在哪

你的任务

遭遇战 → 获得技能

情景：石碑上的斐波那契谜题

常见陷阱

1. DP 三要素——面试官的灵魂拷问

1.1 重叠子问题（Overlapping Subproblems）

1.2 最优子结构（Optimal Substructure）

1.3 状态转移方程（State Transition）

2. Memoization vs Tabulation

3. 经典序列问题

3.1 打家劫舍（House Robber）

3.2 三种经典序列 DP 对比

4. 路径问题——二维 DP 的经典范本

4.1 网格路径（Unique Paths）

4.2 最小路径和（Min Path Sum）

5. 0-1 背包——DP 入门的试金石

6. 双序列 DP

6.1 最长公共子序列（Longest Common Subsequence, LCS）

6.2 最长递增子序列（Longest Increasing Subsequence, LIS）

专题深入：区间 DP

专题深入：状态压缩 DP——TSP 入门

通关挑战

挑战 1：零钱兑换（Coin Change）

挑战 2：编辑距离（Edit Distance）

验收标准

常见卡点

现在不需要理解

旅人笔记

下一站预告