70. 爬楼梯

难度：🟢 Easy | 标签：动归、斐波那契 | 状态：⬜ LeetCode 链接

思路

dp[i] = dp[i-1] + dp[i-2]（最后一步是 1 阶或 2 阶）。 等价于斐波那契。

代码

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; ++i) {
            int c = a + b;
            a = b; b = c;
        }
        return b;
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• dp[1] = 1, dp[2] = 2，注意初值
• 滚动两变量即可
• 通项 / 矩阵快速幂 O(log n)，进阶才需要