01先从一个问题出发
每次能走 1 级或 2 级台阶,到达第 n 级有几种不同走法?
n=4,dp[i] 计数恰好到第 i 级的走法。
先列小答案,再寻找分类方式
一次走 1 或 2 级台阶,走法中的顺序不同算不同方案。n=3 时有 1+1+1、1+2、2+1 三种。我们问的是方案数,不是最少步数,也不是列出所有方案。
考虑任意到达第 n 级的走法,最后一步只能走 1 或 2。前一种走法来自 n−1 级的任意合法走法,后一种来自 n−2 级。两类最后一步不同,不会重复;又覆盖所有可能,所以可以把方案数相加。
递归树里,重复的是同一个问题
直接递归 ways(4)=ways(3)+ways(2),而 ways(3) 又调用 ways(2)+ways(1)。两个 ways(2) 的输入与问题完全相同,没有必要算两遍。注意这是『相同状态』,不是两个结果碰巧相等。
定义 dp[i] 为恰好到达第 i 级的方法数。以递增 i 填表,每次所需的 dp[i−1]、dp[i−2] 已算好。dp[0]=1 表示唯一的空走法;否则到达第 2 级的『直接走两级』会找不到一个合法起点贡献。
先写清模型,再压缩空间
一个 DP 至少应回答五件事:状态是什么、转移为什么成立、初值是什么、以什么顺序计算、最终读哪一项。先用表格把这些关系做对,再观察只依赖最近两项,决定用两个变量代替整张表。
不能见到最优值或计数就机械套这个递推。若每次可走 1 或 3 级,依赖变成 i−1 和 i−3;若有不能踩的台阶,对应状态要为 0;若问最少步数,合并候选应使用 min 并加一步。模型决定公式。
02最直接的办法,为什么慢?
递归尝试最后一步走 1 级或 2 级。
ways(n−2) 等子问题会出现在多个分支中,被重复求解。
03一步步,推导出优化思路
先定义每个状态的含义
定义状态:dp[i] 是恰好走到第 i 级的方法数。
按最后一步分类,得到转移
按最后一步分类,两类互斥且覆盖全部走法:dp[i]=dp[i−1]+dp[i−2]。
从空路径开始,按依赖顺序填表
设置 dp[0]=1,按台阶数递增计算,确保依赖已经就绪。
计算 dp[i] 时,所有更小下标的状态已经正确计算。
拿一个小输入,逐步手算
n=4,dp[i] 计数恰好到第 i 级的走法。
| i | 最后一步为 1 的贡献 | 最后一步为 2 的贡献 | dp[i] |
|---|---|---|---|
| 0 | 空走法 | — | 1 |
| 1 | dp[0]=1 | 不存在 | 1 |
| 2 | dp[1]=1 | dp[0]=1 | 2 |
| 3 | dp[2]=2 | dp[1]=1 | 3 |
| 4 | dp[3]=3 | dp[2]=2 | 5 |
5 种走法为 1111、112、121、211、22。112、121、211 的步长数量一样,但顺序不同,在本题模型中是不同方案。
无重无漏的分类,比背公式更重要
- 基础状态 dp[0]=1 表示空路径,dp[1]=1 表示唯一的一步。
- 把到达 i 的走法按最后一步大小分成互斥的两类。删除最后一步分别与到 i−1、i−2 的走法一一对应,因此相加正确。
- 按 i 递增填表,所有依赖都已经正确计算。由归纳可知 dp[n] 就是题目所求,而不是整张表的和。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
dp[i] = dp[i − 1] + dp[i − 2] · 橙色格正在计算
dp[i] 表示到达第 i 级台阶的方法数,先全部初始化为 0。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
dp = [0] * (n + 1)- 包括状态 0 到 n,一共 n+1 个状态。分配 n 项会在写 dp[n] 时越界。
dp[0] = 1- 这是计数模型的单位起点,不是『有一级楼梯』。本课明确允许 n=0,返回唯一空走法的数量 1。
dp[step] = dp[step - 1]- 先计入最后走 1 级的方案。step=1 时已经足够,不应读负下标 dp[−1]。
if step >= 2:- 只在最后一步可以合法走 2 级时,加入 dp[step−2]。条件体现了可达范围。
05复杂度,来自具体的工作量
只有 n+1 个不同状态,每个状态最多做一次加法,因此 O(n)。这里按定长整数运算计数;任意精度整数的位成本需要另算。
表格保存 n+1 个状态。由于只依赖前两项,可进一步用两个变量压缩为 O(1) 辅助空间。
把工作量具体数出来
朴素递归的调用树分叉,时间可用 O(2^n) 作为上界;记忆化和表格法只求解 n+1 个不同状态,每个做常数次转移,按定长加法计 O(n)。
表格保存 n+1 项,空间 O(n)。若只需最终数量,可保留前两项,辅助空间 O(1);若要回看表格或重建方案,可能仍需更多记录。
结果数值很快增大。Python 大整数的加法不是永远常数成本;C++ 和 JavaScript 还各有数值范围限制。本页实验 n≤20,避免把溢出误认成算法问题。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
状态含义先说清
dp[i] 是方案数,不是最少步数;不同目标对应不同转移。
初始化也是模型一部分
dp[0]=1 表示唯一的空路径,否则无法统一计算最初状态。
先证明分类无重无漏
相加时两类走法必须互斥;状态不能遗漏影响未来的信息。
把 dp[0] 设成 0 会丢掉合法方案
若 dp[0]=0 且按本课代码逐项计算,dp[1]=0,dp[2]=0,所有项都会成为 0。甚至手设 dp[1]=1,也会漏算从起点直接跨两级的方案。
怎样修正:把每个初值翻译成题意,而不是照抄常见的 0 或 1;计数中的空选择有时贡献 1,最小代价问题中的起点则常贡献 0。
08把想法带进真实题目
改变题目,自己改转移
现在每次可以走 1 或 3 级。定义同样的 dp[i],求 dp[0] 到 dp[4],并列出到第 4 级的全部走法。
需要一点提示
最后一步改成 3,只有 i≥3 时才加入 dp[i−3]。
查看完整推导与答案
- dp[0]=1;dp[1]=1,dp[2]=1。
- dp[3]=dp[2]+dp[0]=2;dp[4]=dp[3]+dp[1]=3。
- 到第 4 级的走法为 1111、13、31。不是把旧公式背得更熟,而是从新的最后一步重新分类。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01dp[0] 为什么等于 1?
02时间从指数降为线性的原因?
03能否只保存最近两项?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。