01 动态规划思想导论：从暴力递归到记忆化搜索再到 DP 表

动态规划思想导论：从暴力递归到记忆化搜索再到 DP 表

摘要

动态规划（Dynamic Programming，DP）是面试中最难、也最值得深入掌握的算法范式。很多人对 DP 的印象是”状态转移方程很难想”，或者”每道题的套路都不一样，很难复用”。本文不从抽象定义出发，而是沿着暴力递归 → 记忆化搜索 → 自底向上 DP 表这条演进路线，用 Fibonacci 数列和爬楼梯两道入门题彻底讲透 DP 的本质。理解这条路线之后，你会发现 DP 其实有极强的规律可循——所有 DP 问题都是在做同一件事：消除重复计算。

---

第 1 章 从一道经典题开始

1.1 斐波那契数列：DP 的原型题

斐波那契数列想必家喻户晓：$F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)$。

大多数教程会直接告诉你”这道题可以用 DP 做，时间复杂度 $O(n)$“。但为什么朴素递归不行？递归和 DP 的关系究竟是什么？回答这两个问题，是理解动态规划的第一步。

先写最直觉的递归解法：

// 朴素递归：直接按数学定义翻译
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

这段代码逻辑无懈可击，但一旦 n 稍大（比如 n = 40），你会发现它慢得令人发指。问题出在哪里？

1.2 递归树：看见重复计算

把 fib(5) 的递归展开成一棵树：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

数一下 fib(3) 被调用了几次：2 次。fib(2) 被调用了几次：3 次。fib(1) 被调用了 5 次。当 n = 40 时，fib(1) 会被调用超过 1 亿次——而每次都重新计算，完全是浪费。

这棵递归树一共有多少个节点？你可以粗略地看出每层节点数大约翻倍，因此总节点数是 $O(2^n)$——指数级复杂度，这正是问题所在。

生产避坑：指数爆炸的递归

凡是递归函数中出现 f(n-1) + f(n-2) 这样”一层调用多个子问题”的模式，就要警惕指数爆炸。不是递归本身有问题，而是未剪枝的递归会产生大量重复计算。

1.3 问题的本质：重叠子问题

上面的递归树揭示了一个核心现象：fib(n) 在被计算时，会多次遇到完全相同的子问题（如 fib(3)）。这就是动态规划适用的第一个条件——重叠子问题（Overlapping Subproblems）。

如果每个子问题只被计算一次，那么递归是完全高效的。但一旦同一个子问题被反复计算，我们就需要一种机制来记录已经计算过的结果，避免重复工作。

---

第 2 章 第一步优化：记忆化搜索

2.1 记忆化的思路

记忆化搜索（Memoization）的思路极其简单：用一个哈希表或数组，把每个子问题的计算结果缓存起来；下次遇到同一个子问题时，直接查表返回，不再递归计算。

// 记忆化递归：用 memo 数组缓存中间结果
int[] memo;
 
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];       // 已计算过，直接返回
    memo[n] = fib(n - 1) + fib(n - 2);       // 首次计算，存入缓存
    return memo[n];
}
 
int fibMain(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);                    // -1 表示未计算
    return fib(n);
}

加了这个 memo 数组，情况发生了根本改变：fib(3) 第一次计算后会存入 memo[3]，之后所有对 fib(3) 的调用都直接返回 memo[3]，不再展开子树。整棵递归树从 $O(2^n)$ 个节点变成了 $O(n)$ 个节点。

2.2 时间复杂度的直觉

记忆化之后，每个子问题 fib(i) 只会被真正计算一次。子问题的总数是 $n+1$ 个（从 fib(0) 到 fib(n)），每个子问题的计算量是 $O(1)$（一次加法 + 两次查表），因此总时间复杂度是 $O(n)$。

空间复杂度是 $O(n)$（memo 数组）加上递归调用栈的深度 $O(n)$，共 $O(n)$。

核心概念：记忆化搜索（Top-Down DP）

记忆化搜索是动态规划的自顶向下实现方式。它从大问题出发，递归拆解为子问题，遇到已计算过的子问题时查表返回。 形式上它仍然是递归，但加入了缓存机制。在很多复杂的 DP 问题中（如区间 DP、树形 DP），记忆化搜索比自底向上的 DP 表更自然，更容易写对。

---

第 3 章 第二步演进：自底向上的 DP 表

3.1 从递归到迭代的转换

记忆化搜索已经够用了，为什么还需要”自底向上的 DP 表”？原因有两个：

原因一：消除递归调用栈开销。 递归有函数调用栈的开销，当 n 很大时（比如 $n=10^6$），调用栈可能会溢出。

原因二：遍历顺序显式化，利于空间优化。 自底向上的方式让我们清楚地看到：计算 fib(n) 只需要 fib(n-1) 和 fib(n-2)，因此可以进一步把空间压缩到 $O(1)$。

自底向上的 DP 表写法：

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];
}

进一步空间优化，只保留最近两个状态：

int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;  // dp[i-2] 和 dp[i-1]
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

3.2 三种方式的对比

方式	时间复杂度	空间复杂度	适用场景
朴素递归	$O(2^n)$	$O(n)$（栈）	只有 $n$ 很小时
记忆化搜索	$O(n)$	$O(n)$（memo + 栈）	子问题依赖复杂、难以确定遍历顺序时
自底向上 DP	$O(n)$	$O(n)$ 或 $O(1)$	子问题依赖关系明确，且可以进一步空间优化时

设计哲学：先写记忆化，再优化为自底向上

在面试和初次解题时，先写记忆化搜索是更稳妥的策略：它的代码结构与递归接近，状态转移方程和递推关系一目了然，出错率低。当记忆化版本通过测试后，再考虑是否需要转换为自底向上版本以节省空间。 不要一开始就强迫自己写自底向上的版本——在问题复杂时，“先自顶向下，再自底向上”是更可靠的工程方法。

---

第 4 章 DP 的两个必要条件

4.1 条件一：最优子结构（Optimal Substructure）

最优子结构的含义：原问题的最优解包含子问题的最优解。换句话说，可以通过组合子问题的最优解来构造原问题的最优解。

斐波那契数列的情况：fib(n) = fib(n-1) + fib(n-2)。fib(n) 的”最优解”（唯一解）由 fib(n-1) 和 fib(n-2) 的解直接决定，满足最优子结构。

更典型的例子是最短路径问题：从 A 到 C 的最短路，必然经过某个中间节点 B，其中 A→B 和 B→C 分别是各自的最短路。这就是典型的最优子结构。

反例：最长简单路径不满足最优子结构。从 A 到 C 的最长简单路（不重复节点的最长路），并不能由 A→B 和 B→C 的最长简单路直接拼接（因为两段路可能共享节点，导致整体不再”简单”）。

核心概念：最优子结构

最优子结构是 DP 可以应用的前提。检验一个问题是否满足最优子结构的方法：假设已知子问题的最优解，问题的最优解能否被这些子问题的最优解唯一确定？如果是，则满足；如果子问题间存在约束（如”不能共享节点”），则不满足。

4.2 条件二：重叠子问题（Overlapping Subproblems）

重叠子问题的含义：在递归求解过程中，相同的子问题会被多次计算。

如果每个子问题只出现一次（如分治法中的二分归并排序——每个元素只属于一个子数组），那么记忆化没有任何收益，用递归就够了。只有当子问题重叠时，缓存才能带来性能提升，DP 才有意义。

设计哲学：DP vs 分治

DP 和分治都是将问题拆解为子问题的策略，区别在于：

• 分治：子问题相互独立，每个子问题只出现一次（如归并排序）
• 动态规划：子问题相互重叠，同一个子问题会被反复用到（如斐波那契） 这就是为什么归并排序不需要 memo，而斐波那契需要 memo——问题的结构不同，解法自然不同。

---

第 5 章 LeetCode 70：爬楼梯

5.1 题目

LeetCode 70 - Climbing Stairs（简单）

你需要爬 $n$ 阶楼梯才能到达楼顶。每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶？

输入: n = 2
输出: 2
解释: 1+1 或 2

输入: n = 3
输出: 3
解释: 1+1+1 或 1+2 或 2+1

5.2 第一步：识别子问题

用最直觉的方式想：要到达第 $n$ 阶，只有两种可能：

• 从第 $n-1$ 阶迈 1 步上来
• 从第 $n-2$ 阶迈 2 步上来

因此，到达第 $n$ 阶的方法数 = 到达第 $n-1$ 阶的方法数 + 到达第 $n-2$ 阶的方法数。

这正是斐波那契数列！（初始条件略有不同：f(1) = 1, f(2) = 2）

5.3 第二步：定义状态

状态：dp[i] = 到达第 $i$ 阶的不同方法数。

状态转移方程：dp[i] = dp[i-1] + dp[i-2]

初始条件：dp[1] = 1（只有 1 种方法），dp[2] = 2（1+1 或 2）

最终答案：dp[n]

5.4 第三步：实现（三种版本对比）

版本一：暴力递归（超时）

public int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);  // O(2^n)，n>40 必超时
}

版本二：记忆化搜索（通过）

public int climbStairs(int n) {
    int[] memo = new int[n + 1];
    return helper(n, memo);
}
 
private int helper(int n, int[] memo) {
    if (n <= 2) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    return memo[n];
}

版本三：自底向上 DP（通过 + 空间最优）

public int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;     // dp[1] = 1, dp[2] = 2
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;  // dp[i] = dp[i-1] + dp[i-2]
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

5.5 爬楼梯的扩展变体

变体一：每次可以爬 1、2 或 3 步

只需把转移方程扩展：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，初始条件相应增加 dp[3] = 4（实际计算：1+1+1, 1+2, 2+1, 3）。

变体二：有些台阶不能踩（带障碍物）

// 假设 blocked[i] = true 表示第 i 阶不能踩
if (blocked[i]) {
    dp[i] = 0;  // 无法到达
} else {
    dp[i] = dp[i-1] + dp[i-2];
}

这个扩展直接引出了矩阵路径 DP中的障碍物处理模式，它们是同一思路的高维推广。

---

第 6 章 系统推导 DP 的四步法

经过前面的分析，可以归纳出一套系统推导 DP 的四步法，几乎适用于所有 DP 问题：

6.1 第一步：识别 DP 适用性

检查两个条件：

1. 问题是否求最优解（最大/最小/最多/最少）或方案数（有多少种）？
2. 递归树中是否存在重叠子问题？

如果两个条件都满足，大概率可以用 DP。

生产避坑：不是所有"最优化"都能用 DP

有些最优化问题不满足最优子结构（如含约束的组合优化 NP 问题），DP 不适用。也有些最优化问题贪心就能解决（如活动选择、最小生成树），不需要 DP。识别”该用什么”是比”会不会写”更重要的能力。

6.2 第二步：定义状态

这是 DP 中最关键、也最考验功力的一步。状态定义错误，后面全错。

状态定义的原则：

• 状态必须能唯一确定一个子问题的答案，且子问题的答案只由状态决定，与”如何到达这个状态的路径”无关
• 状态的维度要恰好够用——维度不足则无法推导，维度过多则空间爆炸
• 通常以”前 $i$ 个元素……”或”区间 $[i,j]$……”或”集合 S 中……”为状态基础

爬楼梯的状态：dp[i] = 到达第 $i$ 阶的方法数。这个定义简洁有力：只需知道当前位置 i，就能描述一个完整的子问题。

6.3 第三步：写出状态转移方程

状态转移方程描述”子问题之间的依赖关系”。写转移方程时，从最后一步的决策出发逆向推导：

• “到达第 $i$ 阶，最后一步是从哪里来的？” → 从 $i-1$ 来，或从 $i-2$ 来
• 因此 dp[i] = dp[i-1] + dp[i-2]

每道 DP 题的转移方程，都来自于”对最后一步决策的穷举”。

6.4 第四步：确定初始条件和遍历顺序

初始条件：最小的子问题（不能再拆分的情况），直接给定答案。对爬楼梯来说是 dp[1] = 1, dp[2] = 2。

遍历顺序：确保计算 dp[i] 时，所有 dp[i] 依赖的子问题已经计算完毕。自底向上的遍历通常是正序（从 dp[1] 到 dp[n]），但区间 DP 是按区间长度从短到长，背包问题的遍历顺序有特殊要求（见背包问题深度解析）。

核心概念：四步法

1. 识别 DP 适用性：重叠子问题 + 最优子结构
2. 定义状态：状态 = 子问题的”参数”，是决定答案的全部信息
3. 写转移方程：对最后一步的决策穷举，找到子问题间的递推关系
4. 初始化 + 遍历顺序：确保计算顺序正确，避免循环依赖

---

第 7 章 LeetCode 509 + 746：深化理解

7.1 LeetCode 509：斐波那契数（完整版）

LeetCode 509 - Fibonacci Number（简单）

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n > 1。

这是斐波那契最直接的实现题，注意几个细节：

public int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

边界处理：n = 0 和 n = 1 必须单独处理，否则循环从 i = 2 开始的逻辑会报错。

7.2 LeetCode 746：使用最小花费爬楼梯

LeetCode 746 - Min Cost Climbing Stairs（简单）

数组 cost[i] 表示从第 i 个台阶出发需要花费 cost[i] 的体力。你可以从台阶 0 或 1 出发，每次可以爬 1 或 2 个台阶。到达楼顶（即数组末尾之后）的最小花费是多少？

输入: cost = [10, 15, 20]
输出: 15
解释: 从台阶 1 出发（花费 15），直接跳到顶部。

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6

状态定义：dp[i] = 到达第 i 个台阶的最小花费（不含从第 i 台阶出发的 cost[i]）。

等等——这里有个陷阱：到达台阶 i 时，花费是出发台阶的 cost，而不是到达台阶的 cost。

更清晰的状态定义：dp[i] = 从第 i 个台阶出发，到达顶部（n）的最小总花费。

但自顶向下更容易出错，不如换一个方向：dp[i] = 到达位置 i 的最小总花费（这里把”顶部”看作位置 n，数组长度为 n）。

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    // dp[i] = 到达第 i 个位置（0-indexed）的最小花费
    // 注意：到达位置 i 要支付 cost[i-1] 或 cost[i-2]（上一个台阶的花费）
    // 实际上到达 i，是从 i-1 花 cost[i-1] 爬 1 步，或从 i-2 花 cost[i-2] 爬 2 步
 
    // 换个思路：dp[i] = 从位置 i 出发到顶部的最小花费
    // 这样状态更直觉
    int[] dp = new int[n + 1];  // dp[n] = 0（已到顶部，花费为 0）
    // 从 n-1 倒推到 0
    for (int i = n - 1; i >= 0; i--) {
        // 从位置 i 出发，可以爬到 i+1 或 i+2
        int step1 = cost[i] + dp[i + 1];                        // 爬 1 步
        int step2 = (i + 2 <= n) ? cost[i] + dp[i + 2] : Integer.MAX_VALUE;  // 爬 2 步
        dp[i] = Math.min(step1, step2);
    }
    return Math.min(dp[0], dp[1]);  // 可以从 0 或 1 出发
}

这个解法的状态转移方向是自顶向下（从终点往起点推），适合正向思维难以建立的情形。但也可以正向推：

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    // dp[i] = 到达位置 i 的最小花费（位置 n 是顶部）
    // 到达 i，要么从 i-1 来（支付 cost[i-1]），要么从 i-2 来（支付 cost[i-2]）
    int[] dp = new int[n + 1];
    dp[0] = 0;  // 从位置 0 出发，初始花费 0
    dp[1] = 0;  // 从位置 1 出发，初始花费 0（题目允许从 0 或 1 开始）
 
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1],  // 从 i-1 爬 1 步来，支付 cost[i-1]
                         dp[i - 2] + cost[i - 2]); // 从 i-2 爬 2 步来，支付 cost[i-2]
    }
    return dp[n];
}

边界分析：为什么 dp[0] = dp[1] = 0？因为题目说”你可以从下标为 0 或 1 的台阶开始爬”，也就是说到达 0 和 1 这两个起始位置是免费的（不需要从任何地方”爬上来”），花费只从迈出第一步时开始计算。

生产避坑：状态定义要精确

“到达第 i 阶”和”从第 i 阶出发”是两种不同的状态定义，对应两种不同的转移方程。在解题时必须明确说明你的状态指”到达”还是”出发”，两者混淆是 DP 初学者最常犯的错误。

---

第 8 章 House Robber：DP 的第一道”真题”

8.1 题目（简版，完整版见下一篇）

LeetCode 198 - House Robber（中等）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统——如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

输入: nums = [1, 2, 3, 1]
输出: 4
解释: 偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。合计金额 = 1 + 3 = 4。

输入: nums = [2, 7, 3, 1, 4, 2]
输出: 13
解释: 偷窃 1 号（金额 2）、3 号（金额 3）、5 号（金额 4）。合计金额 = 9。（还不是最优）
     实际最优：偷窃 2 号（7）+ 5 号（4）= 11，或者 1号（2）+3号（3）+5号（4）= 9，
     或者 2 号（7）+ 4 号（1）+ ... 
     实际上最优解是 2+7 中取最优：偷 nums[1]=7 和 nums[4]=4，共 11。不对...
     让我重算：[2,7,3,1,4,2] 最优是偷 7+1+2=10，或者 2+3+4=9，或者 7+4=11，或者 2+1+2=5...
     偷 7+4=11 是最优吗？偷 idx=1(7) + idx=4(4) = 11，中间跳过了 idx=2 和 idx=3，没有相邻，合法，是最优。
     答案：11

8.2 四步法推导

第一步：识别。求”最大金额”→ 最优化问题。且存在重叠子问题（见下面的递归树分析）。✅ 适合 DP。

第二步：定义状态。dp[i] = 偷到第 i 间房屋时（包含第 i 间），能偷到的最大金额。

第三步：转移方程。对第 i 间房，有两个选择：

• 偷：那么第 i-1 间必须跳过，最大金额是 dp[i-2] + nums[i]
• 不偷：那么第 i 间不贡献金额，最大金额是 dp[i-1]（前 i-1 间的最优解）

取两者最大值：dp[i] = max(dp[i-2] + nums[i], dp[i-1])

第四步：初始化 + 遍历。

• dp[0] = nums[0]（只有一间房，偷它）
• dp[1] = max(nums[0], nums[1])（两间房，偷金额大的那间）
• 正序遍历从 i = 2 到 n - 1

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
 
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
 
    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1],           // 不偷第 i 间
                         dp[i - 2] + nums[i]); // 偷第 i 间
    }
    return dp[n - 1];
}

同样可以空间压缩：

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
 
    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);
 
    for (int i = 2; i < n; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

8.3 为什么这道题的状态定义至关重要

有人会问：能不能把状态定义为 dp[i] = “恰好偷了第 i 间的最大金额”（区别于”前 i 间中的最大金额”）？

可以！这样的定义叫做”以某元素结尾的最优解”，转移方程变为：

dp[i] = max(dp[j] + nums[i])   对所有 j <= i-2

这是合法的，但时间复杂度升到了 $O(n^2)$——每个 dp[i] 都要遍历所有 j。

原来的定义 dp[i] = “前 i 间中的最大金额”更聪明：它隐式地考虑了”不偷第 i 间”的情况（dp[i] = dp[i-1]），从而把 $O(n^2)$ 降到了 $O(n)$。

这就是状态定义的艺术：一个好的状态定义，往往能让转移方程更简洁，从而带来更好的时间复杂度。

---

第 9 章 面试中的 DP 思维流程

9.1 遇到陌生题目的破题步骤

1. 读题，判断是否是最优化/计数问题：如果是，考虑 DP
2. 找出”最后一步”的决策：对于数组末尾的元素/区间的右端点/序列的最后一个字符，分析它有哪些选择
3. 从”最后一步的选择”推出子问题：每种选择对应一个子问题，子问题要比原问题”小”
4. 定义状态：用最少的维度描述子问题，使得相同参数对应相同答案
5. 写转移方程：对最后一步的所有选择取最优
6. 确定初始值和遍历顺序

9.2 常见的”DP 陷阱”及规避

陷阱一：状态定义不够精确导致转移歧义

例如，在打家劫舍中，如果把状态定义为 dp[i] = “从第 i 间房开始能偷到的最大金额”（从后向前），在写转移方程时容易混淆”从 i 出发”和”到达 i 时”的差异。建议初学者统一用”前 i 个元素的最优解”这种正向定义。

陷阱二：遗漏边界初始化

自底向上的 DP 必须在循环开始前设置好初始值（dp[0], dp[1] 等）。初始值遗漏或设置错误，会导致整个 DP 表的值全部错误，且这种错误很难通过简单测试用例发现。

陷阱三：转移方向和遍历方向不一致

如果 dp[i] 依赖 dp[i+1]（向右依赖），必须从右往左遍历；如果依赖 dp[i-1]（向左依赖），必须从左往右遍历。背包问题的一维优化中，0-1 背包需要逆序遍历容量，这是因为转移依赖”上一行”而非”同一行”——细节见背包问题深度解析。

陷阱四：“选或不选”和”选哪个”的混淆

许多 DP 题的核心决策是”对于当前元素，选它还是不选它”。这类题的转移方程通常是 dp[i] = max(dp[i-1], dp[i-2] + val)。另一类题的核心决策是”当前元素能从哪些之前的元素转移过来”，如 LIS 中的 dp[i] = max(dp[j]+1) for j < i and a[j] < a[i]。不要把两种模式混用。

---

第 10 章 本章小结与专栏展望

10.1 本章核心总结

概念	关键要点
暴力递归的问题	递归树中存在大量重叠子问题，导致指数级时间复杂度
记忆化搜索	自顶向下，用 memo 缓存子问题结果，把指数降为多项式
自底向上 DP	从最小子问题出发逐步计算，遍历顺序由依赖关系决定
最优子结构	原问题最优解可由子问题最优解构造，DP 的核心前提
重叠子问题	同一子问题被反复求解，是 DP 优化递归的必要条件
四步法	识别 → 定义状态 → 转移方程 → 初始化 + 遍历顺序

10.2 后续内容预告

• 一维线性DP：「选或不选」框架与打家劫舍系列：将打家劫舍从单行扩展到环形数组，以及 Delete and Earn 的转化技巧
• 背包问题深度解析：0-1背包、完全背包与空间压缩：为什么 0-1 背包要逆序遍历、完全背包要正序遍历？从一维滚动数组的维度彻底讲清楚
• 子序列DP：最长递增子序列与 O(nlogn) 优化：patience sorting 思想如何把 $O(n^2)$ 降为 $O(n\log n)$

本文建立的”四步法”和”三种实现方式”框架，在后续每一篇文章中都会被反复使用。打好这个基础，后面的题目分析将事半功倍。