爬楼梯 图解题解

这道题到底在问什么

n

5

输出

8

最优解：一步一步想明白

1. 3最直接的想法是递归 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 一大调用数指数膨胀。慢就慢在重复子问题。
2. 4想到第 i 阶，最后一步要么从 i-1 阶跨 1 阶上来，要么从 i-2 阶跨 2 阶上来，所以 dp[i] = dp[i-1] + dp[i-2]。为什么能记表？每个 dp[i] 只算一次存进表，后面直接查，把递归里重复算的子问题省成一次——这就是「状态转移」加「记表」。
3. 5dp[i] = 到第 i 阶的方法数表固定 1 行 6 列，dp[i] 表示「到第 i 阶有几种走法」。咱从左到右把这一行填满。
4. 6dp[0] = 1第 0 阶就是起点，「待在原地不动」算 1 种走法，dp[0] = 1。这是不依赖别人的地基。
5. 7dp[1] = 1到第 1 阶只有 1 种走法(跨 1 阶)，dp[1] = 1。dp[0]、dp[1] 是两块「地基」，直接给定，不用算。
6. 8dp[2] = dp[1]+dp[0] = 2从这一格起，每个值都等于前两格之和：dp[2] = dp[1] + dp[0] = 1 + 1 = 2。两块依赖格(dep)亮起来。
7. 9dp[3] = dp[2]+dp[1] = 3依赖格往右滑一格：dp[3] = dp[2] + dp[1] = 2 + 1 = 3。注意 f(3) 在递归里要算好几遍，这里只算这一次。
8. 10dp[4] = dp[3]+dp[2] = 5同样规则：dp[4] = dp[3] + dp[2] = 3 + 2 = 5。
9. 11dp[5] = dp[4]+dp[3] = 8dp[5] = dp[4] + dp[3] = 5 + 3 = 8。最后一格填好了。
10. 12dp[5] = 8表格最后一格 dp[5] = 8 就是答案。整行 1、1、2、3、5、8 每个值都只算了一次。
11. 131、1、2、3、5、8——每个数都是前两个之和。这就是斐波那契，DP 的最佳入门例子。
12. 16找到「当前格和前面格的关系」，再从地基填到目标——这就是 DP。打家劫舍、泰波那契都是同一套。
13. 22① 递归为什么慢、怎么救？——f(n)=f(n-1)+f(n-2) 有大量重复子问题，加「记忆化」缓存、或改成递推填表即可。② 空间能更省吗？——能：dp[i] 只依赖前两格，用两个变量滚动，空间从 O(n) 降到 O(1)（上面代码就是）。③ 为什么循环从 i=2 开始？——dp[0]、dp[1] 是 base 直接给定，从 2 起才有「前两格」可加。
14. 23「定义 dp、写递推、定 base、定顺序」这四步是所有一维 DP 的通法：LC198 打家劫舍把递推换成 dp[i]=max(dp[i-1], dp[i-2]+nums[i])、LC746 最小花费爬楼梯、LC1137 泰波那契……只是递推式不同，骨架一模一样。更多在 动态规划专题 继续。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def climbStairs(self, n):
        a, b = 1, 1        # 两块地基滚动
        for _ in range(n):
            a, b = b, a + b  # 前两格之和
        return a

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        for (int i = 0; i < n; i++) {
            int t = a + b;   // 前两格之和
            a = b; b = t;
        }
        return a;
    }
};

class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1;
        for (int i = 0; i < n; i++) {
            int t = a + b;   // 前两格之和
            a = b; b = t;
        }
        return a;
    }
}

# 1.定义 dp[i] 含义  2.写递推  3.定 base  4.定遍历顺序
dp = [0]*(n+1)
dp[0], dp[1] = 1, 1          # base case
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]   # 递推
return dp[n]

vector<int> dp(n + 1);
dp[0] = dp[1] = 1;            // base
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2]; // 递推
return dp[n];

int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;            // base
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2]; // 递推
return dp[n];

复杂度

面试官可能追问