10、爬楼梯

哈喽，大家好，我是厨子，今天给大家分享一下经典题目，爬楼梯

https://leetcode.cn/problems/climbing-stairs/

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1:

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
方法一：1 阶 + 1 阶
方法二：2 阶

示例 2:

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
方法一： 1 阶 + 1 阶 + 1 阶
方法二： 1 阶 + 2 阶
方法三： 2 阶 + 1 阶

示例 3:

输入：n = 4
输出：5
解释：有五种方法可以爬到楼顶。
方法一： 1 阶 + 1 阶 + 1 阶 + 1 阶
方法二： 1 阶 + 1 阶 + 2 阶
方法三： 1 阶 + 2 阶 + 1 阶
方法四： 2 阶 + 1 阶 + 1 阶
方法五： 2 阶 + 2 阶

约束条件:

• 1 <= n <= 45

爬楼梯的规律

问题分析

如何到达第 n 阶？

思路：
要到达第 n 阶，只有两种可能：
1. 从第 n-1 阶爬 1 步
2. 从第 n-2 阶爬 2 步

因此：
到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数

即：f(n) = f(n-1) + f(n-2)

这就是斐波那契数列！

规律推导

n = 1: 只有一种方法
  1

f(1) = 1


n = 2: 有两种方法
  1. 1+1
  2. 2

f(2) = 2


n = 3: 有三种方法
  1. 1+1+1
  2. 1+2
  3. 2+1

f(3) = f(2) + f(1) = 2 + 1 = 3


n = 4: 有五种方法
  从 n=3 的每种方法后面加 1:
    1. 1+1+1 + 1
    2. 1+2 + 1
    3. 2+1 + 1

  从 n=2 的每种方法后面加 2:
    4. 1+1 + 2
    5. 2 + 2

f(4) = f(3) + f(2) = 3 + 2 = 5


递推公式：
f(n) = f(n-1) + f(n-2)
初始条件：f(1) = 1, f(2) = 2

其实很容易理解，因为你每次只能爬 1-2 阶台阶，共 n 个台阶，当你处于第 n-1 和 第 n-2 阶台阶时，均可以直接登到第 n 阶台阶，所以 f(n) = f(n-1)+f(n-2)

为什么是斐波那契数列？

对比：

爬楼梯：
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

斐波那契：
F(1) = 1
F(2) = 1  ← 唯一区别
F(n) = F(n-1) + F(n-2)

结论：
爬楼梯问题的解 = 斐波那契数列向后偏移一位
f(n) = F(n+1)

即：
f(1) = F(2) = 1
f(2) = F(3) = 2
f(3) = F(4) = 3
f(4) = F(5) = 5

解题思路

动态规划⭐

使用 DP 数组自底向上求解。

DP 五部曲

1. 确定 dp 数组及下标含义
   dp[i] 表示到达第 i 阶的方法数

2. 确定递推公式
   dp[i] = dp[i-1] + dp[i-2]

3. dp 数组如何初始化
   dp[1] = 1
   dp[2] = 2

4. 确定遍历顺序
   从前往后，i 从 3 到 n

5. 举例推导 dp 数组
   n = 5
   dp[1] = 1
   dp[2] = 2
   dp[3] = 3
   dp[4] = 5
   dp[5] = 8 ✓

详细图解示例

计算到达第 5 阶的方法数：

步骤1: 初始化
dp[1] = 1
dp[2] = 2
dp = [0, 1, 2, ?, ?, ?]

步骤2: 计算 dp[3]
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp = [0, 1, 2, 3, ?, ?]

步骤3: 计算 dp[4]
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp = [0, 1, 2, 3, 5, ?]

步骤4: 计算 dp[5]
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
dp = [0, 1, 2, 3, 5, 8]

结果: dp[5] = 8 ✓

方法数对应：
n=5 的 8 种方法：
1. 1+1+1+1+1
2. 1+1+1+2
3. 1+1+2+1
4. 1+2+1+1
5. 2+1+1+1
6. 1+2+2
7. 2+1+2
8. 2+2+1

代码实现

class Solution {
public:
    int climbStairs(int n) {
        // 特殊情况
        if (n <= 2) {
            return n;
        }

        // 创建 dp 数组
        vector<int> dp(n + 1);

        // 初始化
        dp[1] = 1;
        dp[2] = 2;

        // 状态转移
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回结果
        return dp[n];
    }
};

时间复杂度: O(n)

空间复杂度: O(n)

动态规划空间优化⭐⭐

观察到当前状态只依赖前两个状态，使用两个变量即可。

代码实现

class Solution {
public:
    int climbStairs(int n) {
        // 特殊情况
        if (n <= 2) {
            return n;
        }

        // 只需要两个变量
        int prev2 = 1;  // dp[i-2]
        int prev1 = 2;  // dp[i-1]

        // 从第 3 阶开始计算
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;  // dp[i] = dp[i-1] + dp[i-2]

            // 滚动更新
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
};

更简洁的写法

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

        return b;
    }
};

时间复杂度: O(n)

空间复杂度: O(1)