子问题视角：分治与动态规划
动态规划解题框架
动规难在哪
不难在代码 —— 动规的代码往往只有十几行。难在从题目到状态转移方程这一步， 而这一步在大多数题解里是跳过的：直接甩出一个方程，说“容易看出”。
本篇要给的不是某道题的解法，是那条被跳过的推导路径。
三个要素
任何一道动规题，最终都要回答三个问题：
- 状态 —— 用什么变量能唯一描述一个子问题？
- 选择 —— 在每个状态下，你能做哪些决策？
- base case —— 最小的子问题是什么，答案是多少？
⭐ 顺序不能反。先想清楚状态是什么，转移方程是状态和选择的自然结果， 不是灵光一现。方程写不出来，九成是状态定义错了，不是脑子不够快。
推导路径：暴力递归 → 备忘录 → 递推
以斐波那契为例（它不是标准动规题，但推导路径一模一样，且没有噪音）。
第一步，暴力递归。 照着定义直译，不考虑效率：
function fib(n) {
if (n === 1 || n === 2) return 1;
return fib(n - 1) + fib(n - 2);
}这一版是指数级的，因为 fib(n-2) 这样的子问题被重复计算了指数次 ——
把递归树画出来就能看到大片重复的子树。这叫重叠子问题，
它正是动规能优化的前提。
⚖️ 常见的说法是「O(2ⁿ)」。那是个合法但不紧的上界 —— 实测调用次数：
| n | 调用次数 | 调用次数 / 2ⁿ |
|---|---|---|
| 10 | 109 | 0.106 |
| 20 | 13,529 | 0.013 |
| 30 | 1,664,079 | 0.0015 |
最后一列一路下降，说明真实底数比 2 小。精确关系是
调用次数 = 2·F(n) − 1（这一篇的 base case 是 F(1)=F(2)=1），
增长底数是黄金比 φ≈1.618。
📌 推导和更多数据在怎么理解递归那一篇。
这里只要记住一点：它是指数级的，具体底数不影响「该上动规」这个判断。
第二步，加备忘录。 算过的存起来：
function fib(n, memo = new Map()) {
if (n === 1 || n === 2) return 1;
if (memo.has(n)) return memo.get(n);
const res = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, res);
return res;
}每个子问题只算一次，复杂度直接降到 O(n)。这一步不需要任何新想法， 只是把递归树上重复的分支剪掉。效果实测：
| n | 暴力 | 备忘录 | 递推 | 滚动变量 |
|---|---|---|---|---|
| 25 | 0.51 ms | 0.0034 ms | 0.0006 ms | 0.0012 ms |
| 30 | 2.92 ms | 0.0018 ms | 0.0004 ms | 0.0013 ms |
| 35 | 33.90 ms | 0.0022 ms | 0.0005 ms | 0.0017 ms |
⭐ n = 35 时暴力比递推慢 约 7 万倍，而后三列几乎分不出高下 ——
从指数降到线性是唯一重要的那一步，后面两步（改递推、压空间）
是常数级的收益。先把重叠子问题干掉，再谈优化。
第三步，改成自底向上的递推。 把递归的方向倒过来：
function fib(n) {
if (n === 1 || n === 2) return 1;
const dp = new Array(n + 1);
dp[1] = dp[2] = 1;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}到这里 dp 数组和状态转移方程就都出来了 —— 它们是推导的产物，不是起点。
🚨 但斐波那契回避了真正的难点
上面那条路径是干净的，因为斐波那契的状态是白送的 —— 题目里就写着 n，
你不用想「用什么变量描述子问题」。
而本篇开头说的是「方程写不出来，九成是状态定义错了」。 所以必须再走一道状态不白送的题。
例：买卖股票，可以交易任意多次
题意复述：给一串每日价格，可以多次买入卖出（但同一时刻手上最多持有一股）， 求最大利润。
先试试最自然的状态定义： dp[i] = 前 i 天能赚到的最多钱。
然后你会卡住 —— 写不出转移方程。因为要决定第 i 天能不能卖，
得知道第 i-1 天手上有没有股票，而 dp[i-1] 这个数字里没有这个信息。
🚨 卡住的位置就是答案：状态少了一个维度。 而这个维度题面里一个字都没提 —— 「持不持股」是你自己发明出来的。
function maxProfit(prices) {
const n = prices.length;
if (n === 0) return 0;
// dp[i][0] = 第 i 天结束时【不持股】的最大利润
// dp[i][1] = 第 i 天结束时【持股】 的最大利润
const dp = Array.from({ length: n }, () => [0, 0]);
dp[0][0] = 0;
dp[0][1] = -prices[0]; // 第一天就买，利润是负的
for (let i = 1; i < n; i++) {
// 今天不持股：昨天就不持 ／ 昨天持股、今天卖了
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// 今天持股：昨天就持有 ／ 昨天不持、今天买了
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0]; // 最后一天手上不该还留着股票
}⭐ 维度补上之后，转移方程几乎是自己写出来的 —— 每个状态只有两个来源， 照着「昨天是什么状态 + 今天做什么选择」列一遍就完了。 这就是「先定状态、方程是产物」的实际含义。
⚠️ return dp[n-1][0] 不能写成 dp[n-1][1]。最后一天还持股意味着钱压在股票里没兑现，
一定不优于卖掉。但代码不会告诉你这一点 —— 返回错的那个只是数字偏小。
实测 3000 组随机价格，与暴力（所有上涨区间求和）对拍：
return dp[n-1][0] 0 / 3000 错
return dp[n-1][1] 2944 / 3000 错（98.1%），且**全部偏小**，没有一个偏大
⚠️ 剩下 56 组（1.9%）答案照样对 —— 都是单元素之类的退化输入⭐ 「全部偏小」不是巧合，是可推导的：dp[i][1] 的定义里减掉了买入价，
它天然不可能超过 dp[i][0]。症状的方向本身就能定位 bug。
📌 这类「状态要多一维」的题非常多：含冷冻期、含手续费、限制交易次数， 都是在这个二维状态上再加一维。认出「一维不够」这件事本身，比记住方程重要。
记忆化搜索 vs 自底向上递推
上面第二步（备忘录）和第三步（递推）都能得到 O(n)，两者不是必须都写。 实际选哪个：
| 记忆化搜索（自顶向下） | 递推（自底向上） | |
|---|---|---|
| 写起来 | 就是暴力递归 + 一行 memo | 要自己想清楚遍历顺序 |
| 遍历顺序 | 不用管，递归自己保证 | ⚠️ 想错就读到还没算的格子 |
| 空间 | 有递归栈，深了会溢出 | 无栈开销，还能状态压缩 |
| 只算用得到的状态 | ⭐ 是（稀疏状态空间时省很多） | 否，全表都要填 |
⭐ 判据：状态转移复杂、遍历顺序不好想的时候用记忆化 （写完暴力递归加一行就完事）；要压缩空间、或者状态空间是密集的方阵，用递推。
⚠️ 「记忆化只算用得到的状态」——省多少完全看状态空间有多稀疏
常见的说法是「有一类题只能用记忆化：状态空间很大但实际可达的状态很少」。 这话对，但没说的是它高度依赖题目。同一个问法（「每次跳 a 或 b 级， 到第 n 级有几种走法」）只改步长：
| 步长 | 目标 | 记忆化实际访问 | 递推必须填 | 差距 |
|---|---|---|---|---|
| 7 / 11 | 300 | 270 | 300 | 1×（毫无优势） |
| 1000 / 1001 | 100,000 | 5,050 | 100,000 | 20× |
| 9973 / 9974 | 1,000,000 | 5,151 | 1,000,000 | 194× |
⭐ 步长小的时候可达状态几乎铺满整个区间，记忆化一点便宜都占不到； 步长大且互质时可达状态极其稀疏，差距才拉开到两个数量级。
二维也一样（每步 +(3,1) 或 +(1,3)，走到 (n,n)）：n=60 时
记忆化访问 325 个状态，递推要填 3721 格 —— 11.4×。
👉 判据不是「状态空间大不大」，是**「可达状态占状态空间的比例」**。 拿不准就估一下：可达状态数远小于表格总格数，才轮到记忆化的这个优势。
状态压缩
注意到 dp[i] 只依赖前两项，那个长度为 n 的数组是浪费的：
function fib(n) {
if (n === 1 || n === 2) return 1;
let prev = 1, curr = 1;
for (let i = 3; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}空间从 O(n) 降到 O(1)。
⚠️ 状态压缩是最后一步优化，不要一上来就想着省空间。 先把正确的 dp 数组写出来，确认逻辑对了，再压。 顺序反过来的话，一旦结果不对，你连“是逻辑错还是压错了”都分不清。
📌 降维的条件、遍历方向怎么定、什么时候不该压，见 状态压缩那一篇。
什么题适合动规
同时满足两条：
- 重叠子问题 —— 递归树上有大量重复计算（否则没得优化）
- 最优子结构 —— 子问题的最优解能推出原问题的最优解
📌 求“最值”的题大多沾动规，但反过来不成立 —— 有些最值问题用贪心或者二分更好。判断依据是上面这两条，不是题干里有没有“最”字。
练习
勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。
- 70. 爬楼梯简单暴力递归 → 备忘录 → 递推，走一遍完整路径
- 198. 打家劫舍中等最简单的一维 dp
- 213. 打家劫舍 II中等环形，拆成两个子问题
- 746. 使用最小花费爬楼梯简单注意 base case
- 62. 不同路径中等二维 dp 入门
⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。