011 · Climbing Stairs
My First Thoughts
第一眼看这个题，很容易把它想成一个排列组合问题：
一共有
n阶楼梯，每次可以走1阶或2阶。那是不是只要看用了几个2，再把这些2和剩下的1排列起来？
比如 n = 4：
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2确实可以这样数。
如果用了 k 个 2，那么这些 2 一共走了 2k 阶，剩下还需要 n - 2k 个 1。
这一组走法里，一共有：
(n - 2k) + k = n - k个步子。
其中要选出 k 个位置放 2，其他位置放 1。所以这一组的数量是：
C(n - k, k)把所有可能的 k 加起来，就能得到答案：
C(n, 0) + C(n - 1, 1) + C(n - 2, 2) + ...这里的 k 最多到 floor(n / 2)，因为 2 的数量不可能超过楼梯阶数的一半。
这个数学思路是对的。
Why That Is Not Enough
不过如果真的按组合公式来写，就需要额外实现组合数计算。
这对这道题来说有点绕。
题目并不要求我们列出所有走法，也不要求我们专门推一个组合公式。它只问：
到第
n阶有多少种方法？
这句话其实更适合从“最后一步”倒着看。
要到达第 n 阶，最后一步只有两种可能：
- 从第
n - 1阶走1阶上来。 - 从第
n - 2阶走2阶上来。
这两类情况不会重叠。
所以，到第 n 阶的方法数，就是：
到第 n - 1 阶的方法数 + 到第 n - 2 阶的方法数也就是：
ways(n) = ways(n - 1) + ways(n - 2)这就是 Fibonacci sequence，也就是斐波那契数列的结构。
最直接的代码可能会写成递归：
def climb_stairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return climb_stairs(n - 1) + climb_stairs(n - 2)这个递归表达了正确的关系，但它会重复计算很多次。
比如计算 climb_stairs(5) 时，会计算：
climb_stairs(4) + climb_stairs(3)而 climb_stairs(4) 里面又会继续计算：
climb_stairs(3) + climb_stairs(2)这里 climb_stairs(3) 已经被重复算了。
当 n 变大时，重复计算会越来越多。
Final Idea
既然每一阶只依赖前两阶，就不需要真的递归展开。
我们可以从小到大算：
ways(1) = 1
ways(2) = 2
ways(3) = ways(2) + ways(1) = 3
ways(4) = ways(3) + ways(2) = 5
ways(5) = ways(4) + ways(3) = 8而且算 ways(i) 的时候，只需要知道：
- 前一阶的方法数
- 前两阶的方法数
所以不需要保存整个数组，用两个变量就够了。
Why It Works
设 prev2 表示到达第 i - 2 阶的方法数，prev1 表示到达第 i - 1 阶的方法数。
那么到达第 i 阶的方法数就是：
current = prev1 + prev2因为最后一步如果走 1 阶，就来自 i - 1；如果走 2 阶，就来自 i - 2。
这两种最后一步不同，所以不会重复计数。
算出 current 后，继续往后推进：
prev2 = prev1
prev1 = current这样每一轮都保持：
prev2是当前目标前两阶的方法数prev1是当前目标前一阶的方法数
直到算到第 n 阶。
Code
def climb_stairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
prev2 = 1
prev1 = 2
for _ in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1Complexity
| Time | \(O(n)\) — 从第 3 阶一路算到第 n 阶 |
| Space | \(O(1)\) — 只保留前两阶的方法数 |
Takeaway
当一个问题看起来像排列组合时，可以先尝试数“用了几个特殊元素”。但如果题目只问总数量，而且当前状态只依赖前面的少数状态，通常可以转成动态规划。这里的关键不是列出所有走法，而是看清楚：到达第
n阶的最后一步，只可能来自第n - 1阶或第n - 2阶。
← Quiz