爬楼梯

最直接的想法是递归 f(n)=f(n-1)+f(n-2)。但 f(5) 要 f(4) 和 f(3)，f(4) 又要 f(3) 和 f(2)……同一个 f(3)、f(2) 会被算很多遍，n 一大调用数指数膨胀。慢就慢在重复子问题。

想到第 i 阶，最后一步要么从 i-1 阶跨 1 阶上来，要么从 i-2 阶跨 2 阶上来，所以 dp[i] = dp[i-1] + dp[i-2]。为什么能记表？每个 dp[i] 只算一次存进表，后面直接查，把递归里重复算的子问题省成一次——这就是「状态转移」加「记表」。

建表：表固定 1 行 6 列，dp[i] 表示「到第 i 阶有几种走法」。咱从左到右把这一行填满。

地基 · dp[0]：第 0 阶就是起点，「待在原地不动」算 1 种走法，dp[0] = 1。这是不依赖别人的地基。

地基 · dp[1]：到第 1 阶只有 1 种走法(跨 1 阶)，dp[1] = 1。dp[0]、dp[1] 是两块「地基」，直接给定，不用算。

dp[2]：从这一格起，每个值都等于前两格之和：dp[2] = dp[1] + dp[0] = 1 + 1 = 2。两块依赖格(dep)亮起来。

dp[3]：依赖格往右滑一格：dp[3] = dp[2] + dp[1] = 2 + 1 = 3。注意 f(3) 在递归里要算好几遍，这里只算这一次。

dp[4]：同样规则：dp[4] = dp[3] + dp[2] = 3 + 2 = 5。

dp[5]：dp[5] = dp[4] + dp[3] = 5 + 3 = 8。最后一格填好了。

答案 = 最后一格：表格最后一格 dp[5] = 8 就是答案。整行 1、1、2、3、5、8 每个值都只算了一次。

1、1、2、3、5、8——每个数都是前两个之和。这就是斐波那契，DP 的最佳入门例子。

找到「当前格和前面格的关系」，再从地基填到目标——这就是 DP。打家劫舍、泰波那契都是同一套。

边界三连：爬楼梯 的边界先看最小规模、特殊输入和最容易触发分支的样例。

① 递归为什么慢、怎么救？——f(n)=f(n-1)+f(n-2) 有大量重复子问题，加「记忆化」缓存、或改成递推填表即可。② 空间能更省吗？——能：dp[i] 只依赖前两格，用两个变量滚动，空间从 O(n) 降到 O(1)（上面代码就是）。③ 为什么循环从 i=2 开始？——dp[0]、dp[1] 是 base 直接给定，从 2 起才有「前两格」可加。

「定义 dp、写递推、定 base、定顺序」这四步是所有一维 DP 的通法：LC198 打家劫舍把递推换成 dp[i]=max(dp[i-1], dp[i-2]+nums[i])、LC746 最小花费爬楼梯、LC1137 泰波那契……只是递推式不同，骨架一模一样。更多在 动态规划专题 继续。

面试追问：爬楼梯 的追问重点，是把动画里的状态定义、边界和复杂度讲成自己的话。