爬楼梯

🟢 Easy · 🏷️ 动态规划 · LeetCode#70

📖 题目

每次可以爬 1 或 2 个台阶，问爬到第 n 阶有多少种不同的方法。

输入	输出	说明
n=3	3	1+1+1、1+2、2+1

💡 思路

站在第 n 阶，上一步只有两种可能：从 n-1 阶跨 1 步，或从 n-2 阶跨 2 步。两种情况互斥，方法数直接相加：f(n) = f(n-1) + f(n-2)（是加法，不是组合出的乘法——"从 n-1 来"或"从 n-2 来"，不是两种走法拼在一起）。

这是动态规划的入门题，套路可以拆成三步：

1. 状态：dp[i] 表示爬到第 i 阶的方法数
2. 转移方程：dp[i] = dp[i-1] + dp[i-2]
3. 初始条件：dp[1]=1, dp[2]=2

直接写递归会严重超时——f(5) 会重复算好几次 f(3)、f(2)，时间复杂度是 O(2ⁿ)。用数组从小到大把每一步的结果存下来才能避免重复计算，降到 O(n)。

💻 代码

基础版：dp 数组

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

时间复杂度 O(n)，空间复杂度 O(n)。

优化版：滚动变量

每一步只用到 dp[i-1]、dp[i-2]，没必要存下整个数组，用两个变量滚动更新就够：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

时间复杂度 O(n)，空间复杂度 O(1)。