LC70
爬楼梯：小机器人有多少种登顶路线？
线性 DP · 最后一步分类可视化:动态规划表n=4 阶楼梯，每次可爬 1 或 2 阶，有多少种不同走法到顶（答案 5）。
时间 O(n)空间 O(1)
题目1 / 10
题目与输入建立输入、目标与算法心智
每次可爬 1 或 2 阶
正在加载算法场景...
当前发生了什么
n=4 阶楼梯，每次可爬 1 或 2 阶，有多少种不同走法到顶（答案 5）。
机器状态
f(i) 定义、枚举路径、最后一步来源、dp 表、prev2/prev1/cur。
为什么正确
先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。
不变量
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 阶楼梯，每次可爬 1 或 2 阶，有多少种不同走法到顶（答案 5）。
机制
先枚举 n=4 建立直觉，再用最后一步分类得 f(i)=f(i-1)+f(i-2)；DP 表记录，滚动变量 O(1) 空间。
机器状态
f(i) 定义、枚举路径、最后一步来源、dp 表、prev2/prev1/cur。
可观察结果
n=4 共 5 种走法；f(5)=8。
不变量
- · f(i) 为到达第 i 阶的方法数；最后一步只来自 i-1 或 i-2，两类互斥且完备。
常见误区
- · f(0) 定义要与 f(1)、f(2) 一致；相加因最后一步分类互斥完备；滚动时先算 cur 再更新。
迁移练习
- · LC198 打家劫舍
- · LC746 最小代价
面试怎么答
定义 f(i)；最后一步来自 i-1 或 i-2 故 f(i)=f(i-1)+f(i-2)；初始化 f(1)=1,f(2)=2；滚动 O(n)/O(1)。