Shouyu

Appearance

爬楼梯 ​

题目描述 ​

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

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

示例 1：

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

题目链接：https://leetcode.cn/problems/climbing-stairs/

文章讲解：https://programmercarl.com/0070.爬楼梯.html

思路 ​

刚开始学习可能考虑到回溯法来穷举所有可能性。

具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上 1 阶或 2 阶，每当到达楼梯顶部时就将方案数量加 1，当越过楼梯顶部时就将其剪枝。

C++
/* 回溯 */
void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
    // 当爬到第 n 阶时，方案数量加 1
    if (state == n)
        res[0]++;
    // 遍历所有选择
    for (auto &choice : choices) {
        // 剪枝：不允许越过第 n 阶
        if (state + choice > n)
            continue;
        // 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res); // 隐藏着回溯
        // 回退
    }
}

/* 爬楼梯：回溯 */
int climbingStairsBacktrack(int n) {
    vector<int> choices = {1, 2}; // 可选择向上爬 1 阶或 2 阶
    int state = 0;                // 从第 0 阶开始爬
    vector<int> res = {0};        // 使用 res[0] 记录方案数量
    backtrack(choices, state, n, res);
    return res[0];
}

回溯的逻辑是把求解问题看作是一步步决策的过程。通过试探和剪枝搜索所有可能的解。

如果把从问题分解的角度分析这道题。设爬到第 i 阶共有 dp[i] 种方案，那么 dp[i] 就是原问题，其子问题包括：

C++
dp[i-1],dp[i-2],dp[i-3],...,dp[2],dp[1]

由于每轮只能上一阶或者二阶，因此我们站在第 i 阶楼梯上时，上一轮只可能站在第 i-1 阶或第 i-2 阶上。换句话说，我们只能从第 i -1 阶或第 i -2阶迈向第 i 阶。

爬到第 i -1 阶的方案数加上爬到第 i -2阶的方案数，就等于爬到第 i 阶的方案数。 递推公式就有了

C++
dp[i] = dp[i-1] + dp[i-2]

所以，各个子问题之间存在的递推关系。

方法一：递归解法（暴力搜索） ​

看到这个递推关系，你可能会想到像上一道题一样的递归写法。

爬楼梯对应递归树

image-20250805150431890

方法二：记忆化搜索 ​

我们希望所有的重叠子问题都被计算一次。因此，声明一个数组 mem 来记录每个子问题的解，在搜索的过程中将重叠的子问题进行剪枝。

  • 首次计算 dp[i] 时记录到 mem[i] ，方便之后使用
  • 如果需要再次计算 dp[i] ，可以直接从 mem[i] 获取结果

记忆化搜索对应递归树

从代码上看递归是在这里int count = dfs(i - 1, mem) + dfs(i - 2, mem); 只有前一个dfs递归时才会进入第二个dfs递归。先往左一个方向递归到底。

方法三：动态规划 ​

前两种方法都是**“从顶至底”的方法**。我们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯逐层收集子问题的解，构建出原问题的解。

与之相反，动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。这里dp数组的作用就和记忆化搜索方法中的mem数组相同。

递归五部曲 ​

1、确定dp数组以及下标的含义 ​

dp[i]： 爬到第i层楼梯，有dp[i]种方法

2、确定递推公式 ​

dp[i] = dp[i-1] + dp[i-2]

3、dp 数组如何初始化 ​

从递推公式看出需要初始化 i=1和i=0时的情况。dp[0]可以认为是0，dp[1]认为是1，i从2开始遍历。可能从题意上不好理解为什么 dp[0]=0 。因为题目提示 i 就不可能为 0！

所以实际上你 i 也可以从 3 开始遍历，这样只需要初始化 dp[1]和dp[2]。

4、确定遍历顺序 ​

从前向后

5、举例推导dp数组 ​

打印即可

代码实现 ​

C++
lass Solution {
public:
    int climbStairs(int n) {
        if(n <= 1) return n;
        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];
    }
}

优化空间复杂度 ​

动规解法一般都可以优化空间复杂度.

后面将讲解的很多动规的题目其实都是当前状态依赖前两个，或者前三个状态，都可以做空间上的优化。这种空间优化技巧被称为“滚动变量”或“滚动数组”。

C++
/* 爬楼梯：空间优化后的动态规划 */
int climbingStairsDPComp(int n) {
    if (n == 1 || n == 2)
        return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}