爬楼梯

爬楼梯到底在数什么

楼梯共 n 阶，每步只能上 1 阶或 2 阶，问从地面走到第 n 阶一共有多少种不同的走法。注意这是一道「数方案数」的题：答案是走法的总数，而不是最少步数，也不是某条具体路线。比如 n = 10 时答案是 89，意味着存在 89 条互不相同的上楼顺序。

为什么不能把所有走法枚举一遍

最直觉的思路是把每一步的选择都展开：每一步有跨 1 阶、跨 2 阶两个分支，一路分叉下去，走法总数随 n 指数级膨胀，逐条枚举根本数不完。慢的根源是重复劳动——无数条路线的后半段其实一模一样，却被一遍遍重数。

关键观察藏在「最后一步」上：不管前面怎么走，落到第 i 阶的最后一步只有两种可能——从第 i-1 阶跨 1 步上来，或从第 i-2 阶跨 2 步上来。于是「到第 i 阶的方法数」就落在「到 i-1 阶」和「到 i-2 阶」这两个更小的问题上，递推能写了。

dp 数组怎么定义，dp[0] 为什么是 1

定义 dp[i] 为「从地面走到第 i 阶的方法数」。起点要铺两个：dp[1] = 1，因为到第 1 阶只有跨一步这一种走法；dp[0] = 1，表示站在地面、一步没走也算一种方案。dp[0] 常被误设成 0，一旦设 0，dp[2] = dp[1] + dp[0] 就会漏掉「直接跨 2 阶」这条路，错误还会一路传染，整张表全部偏小。

为什么两条来路直接相加不重不漏

加法成立的依据是分类计数：按「最后一步跨几阶」把到达第 i 阶的所有走法分成两堆——最后跨 1 阶的，前半程恰好是一条到 i-1 阶的走法；最后跨 2 阶的，前半程恰好是一条到 i-2 阶的走法。两堆的最后一步不同，不可能有同一条走法被数两次；而最后一步只有这两种可能，也不会有走法被漏掉。这题是数方案不是求最优，转移用加法而不是 min 或 max——同一张递推表换成取最小值，就变成另一类问题了。

拿 n=10 把递推填一遍

亲手填一遍表就彻底通了。地面 dp[0] = 1，第 1 阶 dp[1] = 1。到第 2 阶：最后一步要么从第 1 阶跨 1、要么从地面跨 2，dp[2] = dp[1] + dp[0] = 2。往后每格都是前两格相加：dp[3] = 3、dp[4] = 5、dp[5] = 8，整串就是 1、1、2、3、5、8、13、21、34、55、89，到 dp[10] = 89，正是答案。滚动优化时只留最近两个数，用 a, b = b, a + b（把 a 换成旧的 b、b 换成两者之和）每轮向前挪一格，整张表根本不必存下来。

复杂度多少，和斐波那契什么关系

从 dp[2] 递推到 dp[n]，每格只做一次加法，时间 O(n)；又因为 dp[i] 只依赖前两项，不必存整个数组，用两个变量轮替即可，空间 O(1)。

递推式 dp[i] = dp[i-1] + dp[i-2] 加上 dp[0] = dp[1] = 1，正是斐波那契数列，所以爬楼梯常被叫作斐波那契的「面试皮肤」。边界上留意 n = 1 要能直接返回 1，循环从第 2 阶才开始。