爬楼梯
Climbing Stairs
本机进度仅保存在当前浏览器
题目描述
你正在爬楼梯，需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶？
示例：n = 3，方法为 1+1+1、1+2、2+1，输出 3。
解题思路
- 到第 n 阶的最后一步只有两种来源：从 n-1 阶爬 1 阶，或从 n-2 阶爬 2 阶，故 f(n) = f(n-1) + f(n-2)，即斐波那契数列。
- 只需最近两个状态，用两个滚动变量替代数组，空间降到 O(1)。
- 这是理解"状态定义 + 转移方程 + 边界"三要素的最小例子。
参考实现
查看参考实现Python · 建议先自行作答
def climbStairs(n):
# f(n) = f(n-1) + f(n-2)，滚动变量省空间
prev, cur = 1, 1
for _ in range(2, n + 1):
prev, cur = cur, prev + cur
return cur