01先从一个问题出发
每次能走 1 级或 2 级台阶，到达第 n 级有几种不同走法？
一个具体的例子
3 级台阶有 1+1+1、1+2、2+1 共 3 种。最后一步不是 1 就是 2，因此 ways(3)=ways(2)+ways(1)。
02最直接的办法，为什么慢？
递归尝试最后一步走 1 级或 2 级。
暴力 · O(2ⁿ) 上界
ways(n−2) 等子问题会出现在多个分支中，被重复求解。
03一步步，推导出优化思路
1
发现可以复用的信息
定义状态：dp[i] 是恰好走到第 i 级的方法数。
2
建立可维护的状态
按最后一步分类，两类互斥且覆盖全部走法：dp[i]=dp[i−1]+dp[i−2]。
3
消除重复工作
设置 dp[0]=1，按台阶数递增计算，确保依赖已经就绪。
贯穿算法的不变量
计算 dp[i] 时，所有更小下标的状态已经正确计算。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Dynamic Programming交互演示
STEP 01 / 160
1
2
3
4
5
6
7
dp[i] = dp[i − 1] + dp[i − 2] · 橙色格正在计算
当前处理已处理 / 已确定未处理
01
dp[i] 表示到达第 i 级台阶的方法数，先全部初始化为 0。
dynamic_programming.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
只有 n+1 个不同状态，每个状态最多做一次加法，因此 O(n)。这里按定长整数运算计数；任意精度整数的位成本需要另算。
辅助空间
表格保存 n+1 个状态。由于只依赖前两项，可进一步用两个变量压缩为 O(1) 辅助空间。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
状态含义先说清
dp[i] 是方案数，不是最少步数；不同目标对应不同转移。
02
初始化也是模型一部分
dp[0]=1 表示唯一的空路径，否则无法统一计算最初状态。
03
先证明分类无重无漏
相加时两类走法必须互斥；状态不能遗漏影响未来的信息。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01dp[0] 为什么等于 1？
02时间从指数降为线性的原因？
03能否只保存最近两项？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。