动态规划 · 入门
从 LC 70 爬楼梯出发，看朴素递归怎么变成 O(n) DP，再压到 O(1) 空间。
1. 核心原理
DP 要解决的问题模板长这样：「一个原问题能拆成结构相同的若干子问题，子问题之间还互相重复出现」。常见三类场景——最值（最大 / 最小代价）、计数（多少种方案）、是否可达（能不能拼出某状态）——都能套这套思路。
为什么暴力递归会爆？
直觉是写递归：把原问题展开成子问题、再展开成更小的子问题，直到边界。但子问题会被重复算很多次——比如算 f(5) 时要算 f(3)、f(4)，算 f(4) 时又要算 f(3)，f(3) 就算了两遍。展开到 n = 45 这种规模，调用次数就是斐波那契本身，约 10⁹ 级别，直接 TLE。
f(5)
├── f(4)
│ ├── f(3) ← 重复
│ └── f(2)
└── f(3) ← 重复
├── f(2)
└── f(1)DP 的关键洞察
既然子问题重复，就算一次存起来，下次直接查表。这个思路演进出三种实现方式：
- 朴素递归：纯展开，无缓存。指数复杂度，仅用于推导。
- 记忆化（自顶向下）：递归 + 缓存。从原问题往下展开，每个子问题只算一次。
- 递推（自底向上）：循环 + 数组。从最小子问题往上填，不用递归栈。
三者答案一致，区别在「先算谁后算谁」+「要不要递归栈」。本章会把 LC 70 用这三种方式各写一遍，看演化过程。
DP 三要素预告
后面 §4 会展开讲，先记一下骨架——任何 DP 题都可以归结为：
| 要素 | 含义 | LC 70 的例子 |
|---|---|---|
| 状态定义 | f(i) 是什么 | f(i) = 爬到第 i 级的方案数 |
| 转移方程 | f(i) 如何用更小的子问题表达 | f(i) = f(i - 1) + f(i - 2) |
| 边界条件 | 最小子问题的值 | f(1) = 1, f(2) = 2 |
写题时先把这三件事在草稿上写清楚，再开始敲代码——80% 的 DP bug 都来自状态定义模糊。
2. 通用模板
一维线性 DP 的骨架——f(i) 只依赖 f(i - 1) 和 f(i - 2)。这是 LC 70 / 198 / 746 共用的形状。每道题就是把转移方程那一行换成自己的逻辑。
# 自底向上（递推）：O(n) 空间
def solve_bottomup(n: int) -> int:
if n <= 1:
return base_case(n)
dp = [0] * (n + 1)
dp[0], dp[1] = base_case(0), base_case(1) # 边界
for i in range(2, n + 1):
dp[i] = transition(dp, i) # 用 dp[i-1]、dp[i-2] 写出 dp[i]
return dp[n]
# 滚动数组：O(1) 空间
def solve_rolling(n: int) -> int:
if n <= 1:
return base_case(n)
prev2, prev1 = base_case(0), base_case(1)
for i in range(2, n + 1):
cur = transition_rolling(prev2, prev1, i)
prev2, prev1 = prev1, cur # 滚动
return prev1// 自底向上（递推）：O(n) 空间
public int solveBottomUp(int n) {
if (n <= 1) return baseCase(n);
int[] dp = new int[n + 1];
dp[0] = baseCase(0);
dp[1] = baseCase(1);
for (int i = 2; i <= n; i++) {
dp[i] = transition(dp, i);
}
return dp[n];
}
// 滚动数组：O(1) 空间
public int solveRolling(int n) {
if (n <= 1) return baseCase(n);
int prev2 = baseCase(0), prev1 = baseCase(1);
for (int i = 2; i <= n; i++) {
int cur = transitionRolling(prev2, prev1, i);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}// 自底向上（递推）：O(n) 空间
int solveBottomUp(int n) {
if (n <= 1) return baseCase(n);
vector<int> dp(n + 1);
dp[0] = baseCase(0);
dp[1] = baseCase(1);
for (int i = 2; i <= n; i++) {
dp[i] = transition(dp, i);
}
return dp[n];
}
// 滚动数组：O(1) 空间
int solveRolling(int n) {
if (n <= 1) return baseCase(n);
int prev2 = baseCase(0), prev1 = baseCase(1);
for (int i = 2; i <= n; i++) {
int cur = transitionRolling(prev2, prev1, i);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}数组初始化要点：
dp[0]、dp[1]直接赋边界值——不要把循环从i = 0起步，否则要在循环里写一堆if i == 0 ...分支。- 计数 DP 用
int即可，但若n ≥ 50且涉及阶乘 / 累加，建议long（Java）/long long（C++）防溢出。 - Python 不用考虑溢出，但要小心
dp = [0] * (n + 1)——n = 0时dp只有一个元素dp[0]，访问dp[1]会越界。
滚动数组优化思路：
转移只回看「相邻 k 项」时，整个 dp 数组没必要保留——f(i) 算完之后 f(i - 3) 之前都用不上了。一维 DP 里 k = 2，两个变量 prev2 / prev1 就够；二维 DP 里如果 dp[i][j] 只依赖 dp[i - 1][.]，可以压成两行。
自顶向下 vs 自底向上对照：
| 维度 | 自顶向下（记忆化） | 自底向上（递推） |
|---|---|---|
| 写法 | 递归 + 缓存 | for 循环 + 数组 |
| 调用模式 | 从 f(n) 倒着展开 | 从 f(1) 顺着填 |
| 优点 | 跟数学定义对应直接 | 没有递归栈，速度常数小 |
| 缺点 | Python 递归栈深、可能爆栈 | 必须想清楚顺序 |
| 适用 | 状态空间不规则、只算少量状态 | 状态空间规则、全部要算 |
3. 母题精讲：LC 70 爬楼梯
链接：LeetCode 70
题意：你站在楼梯底下，要爬到第 n 级。每一步只能爬 1 级或 2 级。问有多少种不同的爬法。
数据范围：
n：1 到 45
示例：
输入：n = 3
输出：3
解释：三种方式
1 + 1 + 1
1 + 2
2 + 1暴力解：朴素递归
直觉很自然——爬到第 n 级的最后一步要么是从第 n - 1 级跨 1 级上来、要么是从第 n - 2 级跨 2 级上来。两类方案不重不漏：
f(n) = f(n - 1) + f(n - 2)
f(1) = 1
f(2) = 2直接翻译成递归：
class Solution:
def climbStairs_naive(self, n: int) -> int:
if n <= 2:
return n
return self.climbStairs_naive(n - 1) + self.climbStairs_naive(n - 2)class Solution {
public int climbStairsNaive(int n) {
if (n <= 2) return n;
return climbStairsNaive(n - 1) + climbStairsNaive(n - 2);
}
}class Solution {
public:
int climbStairsNaive(int n) {
if (n <= 2) return n;
return climbStairsNaive(n - 1) + climbStairsNaive(n - 2);
}
};代码正确，但只能跑到 n ≈ 30 就开始肉眼可见地变慢。原因是这棵递归树指数膨胀——f(5) 会算两次 f(3)、四次 f(2)、三次 f(1)，等等。展开整棵树：
f(5)
/ \
f(4) f(3)
/ \ / \
f(3) f(2) f(2) f(1)
/ \
f(2) f(1)f(3) 在这棵小树里就算了 2 次；n = 45 时 f(2) 会被算 f(45) ≈ 1.1 × 10⁹ 次（这正是斐波那契数列）。复杂度 O(2ⁿ)，n = 45 时大约 3 × 10¹³ 次调用——直接卡死。
关键观察：子问题在重复计算
朴素递归的浪费就一个字：重。f(3) 不管被谁问到都返回 3，没必要每次重新算。
第一个改进是记忆化——把每个 f(k) 的结果存进缓存，下次问到同一个 k 时直接返回。
from functools import cache
class Solution:
def climbStairs_memo(self, n: int) -> int:
@cache
def f(k: int) -> int:
if k <= 2:
return k
return f(k - 1) + f(k - 2)
return f(n)class Solution {
private int[] memo;
public int climbStairsMemo(int n) {
memo = new int[n + 1];
return f(n);
}
private int f(int k) {
if (k <= 2) return k;
if (memo[k] != 0) return memo[k]; // 缓存命中
return memo[k] = f(k - 1) + f(k - 2);
}
}class Solution {
public:
int climbStairsMemo(int n) {
memo.assign(n + 1, 0);
return f(n);
}
private:
vector<int> memo;
int f(int k) {
if (k <= 2) return k;
if (memo[k] != 0) return memo[k]; // 缓存命中
return memo[k] = f(k - 1) + f(k - 2);
}
};每个 f(k) 只算一次，复杂度直接降到 O(n)。空间是 O(n) 的缓存 + O(n) 的递归栈。
关键观察：递归栈可以拆掉
继续看上面的记忆化版——它仍然是「自顶向下」的递归：f(n) 等 f(n-1)，f(n-1) 等 f(n-2) ……一路压栈到 f(1)、f(2)，再回头填表。
但如果反过来呢？从 f(1)、f(2) 开始，自底向上直接填一个数组：
class Solution:
def climbStairs_tab(self, n: int) -> int:
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]class Solution {
public int climbStairsTab(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}class Solution {
public:
int climbStairsTab(int n) {
if (n <= 2) return n;
vector<int> dp(n + 1, 0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};时间还是 O(n)，但没有递归栈了。n = 10⁶ 也不会爆栈。这就是 tabulation（递推）。
关键观察：状态只依赖最近两项
再看转移方程 dp[i] = dp[i - 1] + dp[i - 2]——dp[i] 只读 dp[i - 1] 和 dp[i - 2] 两项。dp[i - 3] 之前的全是历史包袱，留着没用。
那为什么要开 O(n) 的数组？用两个变量轮换即可：
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2 # dp[1], dp[2]
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2; // dp[1], dp[2]
for (int i = 3; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2; // dp[1], dp[2]
for (int i = 3; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};时间 O(n)、空间 O(1)。同样的题，从 O(2ⁿ) 时间一路压到 O(n) 时间 O(1) 空间——四步走完。
这套「朴素递归 → 记忆化 → 递推 → 滚动数组」就是 DP 入门最经典的一条优化链。下面把这件事抽象一下。
4. 抽象：DP 三步走 + 自顶向下 vs 自底向上
三步走：状态 → 转移 → 顺序
不管题目长什么样，DP 都是三件事拼出来的：
第一步：定义状态。 给一个问题起一个名字，比如 f(i) = 「爬到第 i 级楼梯的方案数」。状态必须满足两个性质：
- 无后效性：
f(i)一旦算出来，后面的状态用f(i)时不需要回头看「f(i)是怎么算出来的」。 - 最优子结构：原问题的答案能由若干子问题的答案直接组合出来。
LC 70 里的 f(i) 满足这两条——爬到第 i 级的方案数只跟「爬到 i - 1、i - 2 级的方案数」有关，跟「i - 1 是怎么爬上去的」无关。
第二步：写转移方程。 用更小的状态把当前状态算出来。LC 70 是 f(i) = f(i - 1) + f(i - 2)。后面 LC 198 打家劫舍是 f(i) = max(f(i - 1), f(i - 2) + nums[i])，LC 746 使用最小花费爬楼梯是 f(i) = min(f(i - 1) + cost[i - 1], f(i - 2) + cost[i - 2])。每道题的差异就在这一行转移方程上。
第三步：决定遍历顺序。 算 f(i) 时必须保证 f(i - 1)、f(i - 2) 都已经算好。对一维线性 DP，最自然的就是「i 从小到大递推」。区间 DP 要按区间长度从小到大、背包 DP 要按物品分层——后面专题会展开。
心智模型：DP = DAG 上的拓扑序递推
三步走背后有一个统一视角：把每个子问题画成 DAG 节点，依赖关系画成有向边，DP 就是沿拓扑序求值。
以 LC 70 为例，节点 f(1)..f(n) 各为一个状态，边 f(i-1) → f(i) 和 f(i-2) → f(i) 表示「算 f(i) 需要先算 f(i-1) 和 f(i-2)」——整张图是个 DAG（无环），拓扑序就是 i 从小到大。
f(1) f(2) f(3) f(4) ... f(n)
\ / \ / \ / \ ...
\ / \ / \ /
↓ ↓ ↓
f(3) f(4) f(5)这个视角立刻把两件事讲清楚：
- 「记忆化 = DFS 后序遍历」：从终点节点开始递归，回溯时填好每个子节点。
- 「递推 = 拓扑序 BFS」：从源点节点开始，按拓扑序逐个填。
两种实现等价，本质都是按 DAG 拓扑序求值。后面所有 DP 专题——背包、区间、状压、树形、数位——都能套这个统一框架，区别只在「DAG 长什么样」。
复杂度公式：状态数 × 单次转移成本
DP 的复杂度有个通用公式：时间 = 状态数 × 单次转移成本。LC 70 状态数 n、单次转移 O(1) → O(n)；后面要讲的 0/1 背包状态数 n × W、转移 O(1) → O(nW)；区间 DP 状态数 n²、转移 O(n) → O(n³)。
记住这个公式，看到题目先估「我需要多少个状态」、再估「算一个状态要多久」，就能判断 DP 能不能过。比如 n = 50、W = 10⁵ 的背包：5 × 10⁶，过；n = 10⁵ 的区间 DP：10¹⁵，不过——这时得换贪心或别的思路。
什么时候用 DP？什么时候不用？
DP 不是默认最优解。判断标准就是三步走前提里的「有重叠子问题 + 最优子结构」是否成立：
| 题目特征 | 适用算法 | 原因 |
|---|---|---|
| 子问题相互无重叠 | 分治 / 递归 | 没有可缓存的重复计算，DP 退化为暴力 |
| 局部最优即全局最优 | 贪心 | 不需要保留多种状态对比，省掉 DP 维度 |
| 单位权图最短路 | BFS | 拓扑层级即步数，DP 杀鸡用牛刀 |
| 有重叠子问题 + 最优子结构 | DP | 经典使用场景 |
| 状态空间指数大 + 无单调性 | 暴力 + 剪枝 / 启发式搜索 | DP 状态数超过内存 |
例如 LC 53 最大子数组和——既能 DP（Kadane 算法），也能分治（O(n log n)）。DP 占优是因为子问题（「以 i 结尾的最大子段和」）数量是 n、转移 O(1)、总 O(n)；分治没用上状态的单调性，常数大。
自顶向下 vs 自底向上
同一个递推关系有两种写法：
| 维度 | 自顶向下（记忆化） | 自底向上（递推） |
|---|---|---|
| 写法 | 递归 + 缓存 | for 循环 + 数组 |
| 调用模式 | 从 f(n) 倒着展开 | 从 f(1) 顺着填 |
| 优点 | 跟数学定义对应直接 | 没有递归栈，速度常数小 |
| 缺点 | Python 递归栈深、可能爆栈 | 必须想清楚顺序 |
| 适用 | 状态空间不规则、只算少量状态 | 状态空间规则、全部要算 |
实战里两种都要会写。记忆化的好处是思维负担轻——把递推方程当成函数写下来、加个 @cache 就完事，正确性几乎不用证明。递推的好处是性能稳定——没有递归调用开销、可以做空间优化。
工程上的建议：
- 面试 30 分钟限时、状态空间结构不复杂——直接写记忆化，定义状态 + 写转移就交卷。
- LC 提交 / 实际工程代码 / 状态多 10⁶ 量级——写递推，顺手做空间优化。
空间优化：滚动数组
一维 DP 里 dp[i] 只依赖 dp[i - 1]、dp[i - 2] 这种「近邻」状态时，没必要开整个数组——几个变量轮换即可。LC 70 / 198 / 746 都符合这个模式，本章后面会把每道题都从 O(n) 空间压到 O(1)。
二维 DP 里如果 dp[i][j] 只依赖 dp[i - 1][.]（上一行）和 dp[i][.]（当前行的左边），可以压成「两行」O(n) 空间；如果只依赖 dp[i - 1][j] 和 dp[i][j - 1]，可以倒着扫压到一行——背包、LCS 这些都用到。这是下一章 背包问题 的核心技巧。
记一个原则：先把朴素 DP 跑对，再考虑压空间。先压空间会让转移方程读不出来，bug 难定位。
5. 例题（三道）
按转移方程复杂度递增排：纯加法 → 二选一带 max → 二选一带 cost。每道题给「朴素 DP + 滚动数组」两版本。
5.1 LC 70 爬楼梯
链接：LeetCode 70
回到本章开头那道题。f(i) = 「爬到第 i 级的方案数」，转移 f(i) = f(i - 1) + f(i - 2)，边界 f(1) = 1、f(2) = 2。
下面用 ArrayViz 走一遍 n = 6 的填表过程，每一格里写的就是 dp[i]：
climbStairs(6) 填表过程
dp[i] = dp[i-1] + dp[i-2]，从左到右
最后 dp[6] = 13——意思是爬到第 6 级有 13 种走法。注意 dp 数组其实就是斐波那契数列 1, 2, 3, 5, 8, 13, ...。
代码（滚动数组版）：
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2 # dp[1], dp[2]
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2 # 同时更新避免覆盖
return prev1class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};时间 O(n)、空间 O(1)。注意 Python 的同时赋值 prev2, prev1 = prev1, prev1 + prev2 会先求右侧再赋左侧，不会有「还没更新就读」的问题；Java / C++ 必须用临时变量 cur。
Follow-up：上面的 f(i) 只是数方案。如果换成「每一级有一个权值，要在不能踩相邻两级的前提下偷最多权值」——状态怎么变？
5.2 LC 198 打家劫舍
链接：LeetCode 198
题意：一排房子排成一条直线，第 i 间房里有 nums[i] 现金。你不能偷相邻两间（会触发警报）。求能偷到的最大金额。
数据范围：
nums.length：1 到 100nums[i]：0 到 400
示例：
输入：nums = [2, 7, 9, 3, 1]
输出：12
解释：偷第 0、2、4 间，金额 2 + 9 + 1 = 12。状态：f(i) = 「考虑前 i + 1 间房（下标 0 到 i），能偷到的最大金额」。
转移：站在第 i 间，有两个选择，取最大：
- 不偷
i：金额跟「考虑前i间」一样，即f(i - 1) - 偷
i：那i - 1不能偷，金额是f(i - 2) + nums[i]
合起来 f(i) = max(f(i - 1), f(i - 2) + nums[i])。
边界：f(0) = nums[0]（只一间房，偷不偷无论怎样最优都是偷），f(1) = max(nums[0], nums[1])。
代码（递推 + 滚动数组两版）：
# 递推版：O(n) 空间
class Solution:
def rob_tab(self, nums: list[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[n - 1]
# 滚动数组版：O(1) 空间
class Solution:
def rob(self, nums: list[int]) -> int:
prev2, prev1 = 0, 0 # f(-2), f(-1) 都是 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1// 递推版：O(n) 空间
class Solution {
public int robTab(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], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
}
// 滚动数组版：O(1) 空间
class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0; // f(-2), f(-1) 都是 0
for (int x : nums) {
int cur = Math.max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}// 递推版：O(n) 空间
class Solution {
public:
int robTab(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
};
// 滚动数组版：O(1) 空间
class Solution {
public:
int rob(vector<int>& nums) {
int prev2 = 0, prev1 = 0; // f(-2), f(-1) 都是 0
for (int x : nums) {
int cur = max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};时间 O(n)、空间 O(1)。
注意滚动数组版的边界处理比朴素版还干净——初始 prev2 = prev1 = 0 直接对应「还没看任何房子」的状态。第一轮 x = nums[0] 时计算 max(0, 0 + nums[0]) = nums[0]，自动等于 f(0)；第二轮 x = nums[1] 时计算 max(nums[0], 0 + nums[1]) = max(nums[0], nums[1])，自动等于 f(1)。用「全 0 起点」代替显式边界是滚动数组 DP 的常用清洁技巧。
LC 70 跟 LC 198 转移方程结构几乎一样——都是 f(i) 依赖 f(i - 1) 和 f(i - 2)，区别只在「求和」vs「max + cost」。这种「二选一型 1D DP」在 LC 简单/中等档里反复出现，滚动数组写法值得记熟。
Follow-up：再变一下题面——不是「偷东西」，而是「爬楼梯但每级有代价」，从 0 或 1 级起步，到达顶部时不需要踩顶层那一级，怎么花最少？
5.3 LC 746 使用最小花费爬楼梯
链接：LeetCode 746
题意：一个数组 cost，cost[i] 表示登上第 i 级楼梯的代价。每步可以爬 1 级或 2 级。起点可以选第 0 级或第 1 级（无代价进入），求登顶（越过最后一级）的最小总代价。
数据范围：
cost.length：2 到 1000cost[i]：0 到 999
示例：
输入：cost = [10, 15, 20]
输出：15
解释：从第 1 级起步（代价 15），跨 2 级到顶。输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：依次踩 0 → 2 → 4 → 6 → 7 → 9，代价 1 + 1 + 1 + 1 + 1 + 1 = 6。状态：f(i) = 「到达第 i 级楼梯（不含踩 i）所需的最小代价」。换句话说，f(i) 是 站到 i 之前所有踩过台阶的代价总和。
转移：到达 i 之前最后一步要么从 i - 1 跨 1、要么从 i - 2 跨 2：
- 从
i - 1跨 1：在i - 1上付代价cost[i - 1]，到达i - 1之前的累计是f(i - 1)，合起来f(i - 1) + cost[i - 1] - 从
i - 2跨 2：类似f(i - 2) + cost[i - 2]
合起来 f(i) = min(f(i - 1) + cost[i - 1], f(i - 2) + cost[i - 2])。
边界：f(0) = f(1) = 0（从 0 或 1 级起步免费）。
答案：f(n)——「登顶」等于「到达第 n 级之前」，因为登顶不需要再踩那一级。
代码：
# 递推版
class Solution:
def minCostClimbingStairs_tab(self, cost: list[int]) -> int:
n = len(cost)
dp = [0] * (n + 1) # f(0) = f(1) = 0
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[n]
# 滚动数组版
class Solution:
def minCostClimbingStairs(self, cost: list[int]) -> int:
prev2, prev1 = 0, 0 # f(0), f(1)
for i in range(2, len(cost) + 1):
prev2, prev1 = prev1, min(prev1 + cost[i - 1], prev2 + cost[i - 2])
return prev1class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int prev2 = 0, prev1 = 0;
for (int i = 2; i <= n; i++) {
int cur = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
int prev2 = 0, prev1 = 0;
for (int i = 2; i <= n; i++) {
int cur = min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};时间 O(n)、空间 O(1)。
这道题真正容易绕晕的地方是状态的定义——f(i) 是「到达 i 之前」还是「踩到 i 之后」？两种定义都能 AC，但转移方程会不一样。本章用的「到达之前」版边界最干净（f(0) = f(1) = 0），后面会沿用这种定义。
另一种定义是 g(i) = 「踩过 i 之后的累计代价」，转移 g(i) = min(g(i - 1), g(i - 2)) + cost[i]，最后答案 min(g(n - 1), g(n - 2))——因为最后一步可以从 n - 1 或 n - 2 跨上顶。两种定义都对，但 g 版的答案处理略麻烦。
对比 LC 70 / 198 / 746 的转移方程：
| 题 | 转移方程 | 边界 |
|---|---|---|
| LC 70 爬楼梯 | f(i) = f(i - 1) + f(i - 2) | f(1) = 1, f(2) = 2 |
| LC 198 打家劫舍 | f(i) = max(f(i - 1), f(i - 2) + nums[i]) | f(0) = nums[0], f(1) = max(nums[0], nums[1]) |
| LC 746 最小花费爬楼梯 | f(i) = min(f(i - 1) + cost[i - 1], f(i - 2) + cost[i - 2]) | f(0) = f(1) = 0 |
三道题的状态空间、转移结构完全同构——都是「f(i) 依赖 f(i - 1) 和 f(i - 2)」——只是聚合函数从「求和」变成「取 max」再变成「取 min + cost」。呼应 §4 的三步走——骨架相同，只是转移方程在变。
6. 边界、易错与复杂度
边界条件：n = 1 / 数组长度 1
LC 70 要求 n ≥ 1，但代码常被写成「dp[2] 直接赋初值」——n = 1 时就会越界。处理方法两种：
- 显式判空：
if n <= 2: return n（推荐，可读性最好） - 把 dp 数组从下标 0 起步：
dp = [0, 1, 2]，循环从i = 3开始（避免特判但要小心 off-by-one）
LC 198 / 746 同理——数组长度 1 时直接返回即可。
滚动数组的同时赋值陷阱
Python 写 prev2, prev1 = prev1, prev1 + prev2 是同时赋值——右侧整体求值后再统一写入左侧，所以 prev1 在右侧表达式里仍然是更新前的值。Java / Go / C++ 没有这个语法，必须显式 int cur = prev1 + prev2; prev2 = prev1; prev1 = cur;，否则会读到已更新的 prev1。
写跨语言代码时容易在这里踩坑。
记忆化的递归栈深度
Python 默认递归栈 1000 层。n = 10⁴ 用 @cache + 递归必爆栈。两个解：
- 改成递推（推荐）—— 几乎所有「线性状态空间」的 DP 都能递推
sys.setrecursionlimit(10**6)顶一下，但内存随之上去
Java / Go / C++ 默认栈深得多，记忆化一般够用。Python 优先递推。
数组下标 vs 状态编号
dp[i] 的 i 含义因题而异——LC 70 里 dp[i] 表示「爬到第 i 级」，LC 198 里 dp[i] 表示「考虑前 i + 1 间房子」，LC 746 里 dp[i] 表示「到达第 i 级之前」。
写题前在草稿纸上写出 dp[i] = ... 的完整中文定义会少踩坑——大部分 DP bug 来自状态定义模糊而非转移方程算错（比如 LC 746 是「到达之前」还是「踩到之后」），导致边界对不上、答案差 1。
自顶向下 vs 自底向上的工程取舍
| 场景 | 推荐方式 |
|---|---|
| 状态空间规则、全要算 | 递推 + 滚动数组 |
| 状态空间稀疏、只问几个 | 记忆化 |
| 转移依赖多个非线性子问题 | 记忆化（避免想清遍历顺序） |
Python 大 n（n > 10⁵） | 递推（避免爆栈） |
| 调试期、想快速验证转移方程 | 记忆化（先正确再优化） |
复杂度速查
| 题 | 时间 | 空间（朴素） | 空间（滚动） |
|---|---|---|---|
| LC 70 爬楼梯 | O(n) | O(n) | O(1) |
| LC 198 打家劫舍 | O(n) | O(n) | O(1) |
| LC 746 最小花费爬楼梯 | O(n) | O(n) | O(1) |
三道题的空间都能压到 O(1)——因为状态依赖只回看两步。
面试官常追问的几个方向
DP 题写完后面试官常追问下面这几类问题，每一类对应一个能立刻给出方向的技巧：
n 大到 10¹⁸ 怎么办（LC 70 进阶）：线性 DP O(n) 还是太慢。LC 70 这种「线性常系数递推」可以用矩阵快速幂压到 O(log n)：
[f(i) ] [1 1] ^ (i-1) [f(1)]
[f(i-1)] = [1 0] · [f(0)]矩阵 2×2 自乘 log(i) 次即可。同样思路适用于斐波那契、跳台阶、字符串递推等任何「f(i) 是前 k 项线性组合」的题型。
状态空间爆炸怎么办（背包/区间 DP 量级超内存）：
- 维度小、值域大 → 状压 DP：用 bitmask 把「已选集合」压到一个 int 里
- 子问题对称 → Meet-in-the-middle：把状态空间一分为二，分别枚举再合并
- 状态稀疏 → map / hashmap 代替数组
有没有闭式解 / 数学公式：能写出递推不一定要写 DP。LC 70 实际上有斐波那契通项 f(n) = (φⁿ - ψⁿ) / √5；某些组合数 DP 直接用阶乘 + 逆元 O(1) 查。面试官追问时先想「是否存在生成函数 / 通项」，能给 senior signal。
能否压到更小空间：滚动数组 → 双变量 → 单变量（Kadane 风格）。再追问可以做 O(1) 额外空间——把答案累积进输入数组本身（in-place DP，比如 LC 53）。
在线/流式输入怎么办：每来一个新元素就增量更新 dp，不要重跑全部。LC 53 的 Kadane 算法就是天然在线版——cur_max = max(num, cur_max + num)，每个元素 O(1) 处理，可支持流式。
8. 小结
动态规划入门的三件事：
- 定义状态：用一句话写清
f(i)是什么，避免歧义 - 写转移方程：用更小的子问题表达
f(i)，每道题的差异都在这一行 - 决定遍历顺序：保证算
f(i)时所需的子问题已经备好
本章五道一线题——LC 70 / 198 / 746 + 加餐 LC 213 / 740——状态空间结构完全同构，都是 f(i) 依赖 f(i - 1) 和 f(i - 2) 的一维 DP，区别只在「求和 / max / min + cost / 环形拆链 / 值域聚合」这一层语义。O(n) → 滚动数组 O(1) 的压缩在后续几乎所有线性 DP 章节都会复用。
LC 53 Kadane / LC 152 双 DP / LC 91 字符串 DP 是同一族的进阶变体——状态定义和转移依赖结构略有不同，但「先朴素再压空间」的工作流完全一致。
下一节 背包问题 把状态空间从一维推到二维——f(i, c) 表示「前 i 个物品、容量 c 时的最优值」，转移变成「选 vs 不选」的二维表。背包是 DP 题里另一族出现频率极高的母题，0-1 / 完全 / 多重 / 分组背包都能用同一份骨架处理。
对应灵神题单：DP 入门 / 1D DP / Fibonacci 型 + 单序列选择型
进一步阅读：灵茶山艾府《动态规划题单》入门部分；LeetCode DP 标签 入门难度