第9章｜动态规划
Unit 01 · LeetCode #70 爬楼梯
不要先背斐波那契，
先看见“最后一步从哪里来”。
本单元把 Unit 00 的状态压缩思想应用到正式题目：先亲自枚举走法，再观察暴力搜索如何重复进入同一台阶，最后把每个台阶压缩成一个计数状态，并进一步只保留未来仍会读取的两个旧值。
已恢复上次学习位置阶段、动画、答题、代码槽位和迁移进度均已恢复。
知识桥梁｜Unit 00 → Unit 01
Unit 00：从当前位置到终点
ways(position) 表示从当前位置继续走到目标的方案数，依赖右侧的后继状态。
同一个问题的另一种坐标系 →
Unit 01：到达当前台阶
dp[i] 表示从地面到达第 i 阶的方案数，依赖左侧两个前驱状态。
本单元贯穿问题计算当前台阶时，哪两类走法按“最后一步”形成互不重叠的完整划分？
LeetCode #70 原题题面转述、示例、约束与函数签名
题目要求
你正在爬一段共有 n 阶的楼梯。每次只能向上走 1 阶或 2 阶。返回到达楼顶的不同走法数量。
class Solution:
def climbStairs(self, n: int) -> int:
pass
约束
1 ≤ n ≤ 45；- 不同走法按步长序列区分，例如
[1,2]与[2,1]是不同方案。
示例
输入：n = 2
输出：2
解释：[1,1]、[2]
输出：2
解释：[1,1]、[2]
输入：n = 3
输出：3
解释：[1,1,1]、[1,2]、[2,1]
输出：3
解释：[1,1,1]、[1,2]、[2,1]
| 方法 | 时间 | 空间 | 教学用途 |
|---|---|---|---|
| 暴力递归 | O(2ⁿ) | O(n) | 看见重复子问题 |
| 记忆化 | O(n) | O(n) | 合并相同状态 |
| 表格 DP | O(n) | O(n) | 明确依赖顺序 |
| 滚动变量 | O(n) | O(1) | 最终提交版本 |
六段认知流程
本环节已完成
请停留观察当前状态，再主动进入下一环节。