爬楼梯：小机器人有多少种登顶路线？

怎样从“n=4 阶楼梯，每次可爬 1 或 2 阶，有多少种不同走法到顶（答案 5）。”推导出 线性 DP · 最后一步分类，并证明每次状态变化都不会漏掉答案？

中心结论：先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数

在本站主例中，n=4 阶楼梯，每次可爬 1 或 2 阶，有多少种不同走法到顶（答案 5）。

算法最终需要得到或观察：n=4 共 5 种走法；f(5)=8。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 f(i) 定义、枚举路径、最后一步来源、dp 表、prev2/prev1/cur。
3. 3转移每一步按照 先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。
4. 4收尾读取 n=4 共 5 种走法；f(5)=8。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：f(i) 定义、枚举路径、最后一步来源、dp 表、prev2/prev1/cur。

简单的 DP，经典的爬楼梯问题。一个楼梯可以由 `n-1` 和 `n-2` 的楼梯爬上来。 这一题求解的值就是斐波那契数列。

先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。

执行过程中持续维护：f(i) 定义、枚举路径、最后一步来源、dp 表、prev2/prev1/cur。

正确性依赖以下不变量：f(i) 为到达第 i 阶的方法数；最后一步只来自 i-1 或 i-2，两类互斥且完备。

面试时可以压缩为：定义 f(i)；最后一步来自 i-1 或 i-2 故 f(i)=f(i-1)+f(i-2)；初始化 f(1)=1,f(2)=2；滚动 O(n)/O(1)。

落到当前题，执行机制可以压缩为：先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入n=4 阶楼梯，每次可爬 1 或 2 阶，有多少种不同走法到顶（答案 5）。 因为：先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。
2. 2dp[i] = 到达第 i 阶的方法数初始化前两阶。 因为：到 i 阶只能从 i-1 或 i-2 来。
3. 3dp[3] = dp[2] + dp[1] = 3状态转移填表。 因为：Fibonacci 型 DP。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5dp[4] = dp[3] + dp[2] = 5状态转移填表。 因为：Fibonacci 型 DP。
6. 6dp[5] = dp[4] + dp[3] = 8状态转移填表。 因为：Fibonacci 型 DP。
7. 7dp[i] = 到达第 i 阶的方法数初始化前两阶。 因为：到 i 阶只能从 i-1 或 i-2 来。
8. 8收尾与复杂度n=4 共 5 种走法；f(5)=8。 因为：时间 O(n) · 空间 O(1)。先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func climbStairs(n int) int {
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

func main() {
    // 1. 主例
    //    输入：mode="climbing-stairs", n=5
    //    期望：n=4 共 5 种走法；f(5)=8。
    //
    // 2. 失败 / 未命中
    //    检查：f(0) 定义要与 f(1)、f(2) 一致；相加因最后一步分类互斥完备；滚动时先算 cur 再更新。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC198 打家劫舍；LC746 最小代价
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意n=4 阶楼梯，每次可爬 1 或 2 阶，有多少种不同走法到顶（答案 5）。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。
4. 4证明f(i) 为到达第 i 阶的方法数；最后一步只来自 i-1 或 i-2，两类互斥且完备。
5. 5复杂度时间 O(n)，空间 O(1)