算法困惑问答 · LC 70 爬楼梯
爬楼梯为什么算出来是斐波那契数列？
直接答案
因为到达第 i 阶的最后一步只有两种可能：从第 i−1 阶跨 1 步上来，或从第 i−2 阶跨 2 步上来。前者有 dp[i−1] 种走法、后者有 dp[i−2] 种，两类没有交集也没有遗漏，所以 dp[i] = dp[i−1] + dp[i−2]——这条递推式和斐波那契一模一样，只是起点是 dp[0] = dp[1] = 1，于是整张表就是 1, 1, 2, 3, 5, 8, …
加法为什么成立：按「最后一步」分类
计数问题能用加法的前提是分类「互斥且穷尽」。按最后一步是 1 阶还是 2 阶分：最后跨 1 步的方案，前面部分恰好是「走到 i−1 阶」的任一种方案；最后跨 2 步的，前面恰好是「走到 i−2 阶」的任一种。一种方案的最后一步不可能既是 1 又是 2（互斥），而最后一步只能是这两者之一（穷尽），所以直接相加不重不漏。
「按最后一步分类」是计数 DP 的万能起手式：零钱兑换按最后用的硬币分、不同路径按最后一步向下还是向右分，套路完全一致。
边界为什么是 dp[0] = 1 而不是 0
dp[0] 表示「站在地面」的走法数，算 1 种（什么都不做）。设成 0 的话 dp[2] = dp[1] + dp[0] = 1，从此整张表偏小甚至全 0。理解方式：dp[0] 承载的是「最后一步恰好跨 2 步直达第 2 阶」这一种方案，它必须记为 1 才能被数进去。
另一个入门翻车点：把加法写成 min 或 max。本题数的是方案数，不是求最优值——转移用加号还是 min/max，取决于题目问「有几种」还是「最好多少」，动手前先看清问句。
代码关键行（Python）
def climbStairs(n):
if n <= 1: return 1
a, b = 1, 1 # dp[0], dp[1]
for _ in range(2, n + 1):
a, b = b, a + b # dp[i] = dp[i-1] + dp[i-2]
return b转移只依赖前两项，两个滚动变量就够，空间从 O(n) 降到 O(1)。`a + b` 这一处加法，背后是「按最后一步分类」的加法原理。
常见追问
一次能爬 1、2 或 3 阶怎么办？
同一套分类多一条来路：dp[i] = dp[i−1] + dp[i−2] + dp[i−3]（俗称「泰波那契」）。边界多铺一个 dp[2]，其余不变。
这题和「使用最小花费爬楼梯」有什么区别？
LC746 问的是最小花费，转移从加法换成 min：dp[i] = min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2])。同一个楼梯模型，「数方案」用加、「求最优」用 min/max，正好练出对转移算子的敏感度。
把这道题彻底吃透
LC 70「爬楼梯」有逐步交互动画和完整图文题解，配着本页的结论看，一遍就通。