(75)爬楼梯

文章目录

• 1. 每日一言
• 2. 题目
• • 2.1 解题思路
  • • 2.1.1 递归
    • 2.1.2 记忆化搜索
    • 2.1.3 动态规划
    • 2.1.4 动态规划空间优化
  • 2.2 代码
  • • 2.2.1 递归
    • 2.2.2 记忆化搜索
    • 2.2.3 动态规划
    • 2.2.4 动态规划空间优化
• 3. 结语

1. 每日一言

Happy life lies in a peaceful mind.
幸福的生活存在于心绪的宁静之中。

2. 题目

题目链接：爬楼梯

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

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

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

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

提示：

1 <= n <= 45

2.1 解题思路

2.1.1 递归

1. 首先，函数判断如果 n 小于等于 2，则直接返回 n。因为在楼梯阶数小于等于 2 的情况下，只有一种方式爬到顶部，即分别走一步或者直接跨两步。

2. 对于大于 2 的情况，函数采用递归的方式进行计算。爬到第 n 阶楼梯的方式数量等于爬到第 n-1 阶和第 n-2 阶的方式数量之和。这是因为爬到第 n 阶楼梯只有两种方式，一种是从第 n-1 阶再爬一阶，另一种是从第 n-2 阶再跨两阶。

3. 最后，将计算得到的方式数量 sum 返回。

2.1.2 记忆化搜索

1. 首先，定义一个全局数组 men，大小为 46（因为题目中规定楼梯数不超过 45）。这个数组用来保存已经计算过的楼梯阶数对应的爬楼梯方式数量，避免重复计算。
2. 接下来定义一个递归函数 climb(int n)，用来计算爬到第 n 阶楼梯的方式数量。如果 n 小于等于 2，则直接返回 n，表示只有一种或两种方式爬到顶部。
3. 如果 men[n] 不为 -1，说明之前已经计算过爬到第 n 阶楼梯的方式数量，直接返回 men[n]。
4. 如果 men[n] 为 -1，说明还没有计算过爬到第 n 阶楼梯的方式数量，此时调用递归函数 climb(n-1) + climb(n-2) 来计算，并将结果保存在 men[n] 中，然后返回该结果。
5. 最后，在 climbStairs 函数中，将 men 数组初始化为 -1，并调用 climb 函数来求解爬楼梯问题。

2.1.3 动态规划

1. 首先，定义一个长度为 46 的整型数组 climb，用来存储爬到每个楼梯阶数的方式数量。数组初始化为 [1, 2]，表示爬到第一阶和第二阶楼梯的方式数量分别为 1 和 2。
2. 接下来，使用一个循环从第三阶楼梯开始计算爬楼梯的方式数量。对于第 i 阶楼梯，爬到这一阶的方式数量等于爬到第 i-1 阶和第 i-2 阶的方式数量之和，因为只有两种方式可以到达第 i 阶楼梯，要么是从第 i-1 阶跨一步，要么是从第 i-2 阶跨两步。
3. 最后，返回数组 climb 中第 n-1 个元素，即爬到第 n 阶楼梯的方式数量。

2.1.4 动态规划空间优化

1. 如果输入的楼梯阶数 n 小于等于 2，那么直接返回 n，因为在这种情况下，只有一阶或者两阶楼梯，爬到顶部的方式数量分别为 1 和 2。
2. 对于大于 2 的情况，定义三个变量 a、b 和 c，分别表示爬到第 n-2、第 n-1 和第 n 阶楼梯的方式数量。初始时，a 被赋值为 1（表示爬到第一阶楼梯的方式数量），b 被赋值为 2（表示爬到第二阶楼梯的方式数量）。
3. 使用一个循环来计算爬到第 n 阶楼梯的方式数量。循环从第 3 阶楼梯开始，依次计算爬到每一阶楼梯的方式数量，直到计算到第 n 阶为止。
4. 在循环中，更新 c 的值为 a + b，然后将 b 的值赋给 a，将 c 的值赋给 b，以便继续下一轮循环。
5. 循环结束后，c 中存储的就是爬到第 n 阶楼梯的方式数量。
6. 最后，返回 c。

2.2 代码

2.2.1 递归

int climbStairs(int n) {
    if(2 >= n) {
        return n;
    }

    int sum = 0;
    sum = climbStairs(n-1) + climbStairs(n-2);
    
    return sum;
}

2.2.2 记忆化搜索

int men[46];
int climb(int n) {
    if(n <= 2) {
        return n;
    }
    if(men[n] != -1) {
        return men[n];
    }
    return men[n] = climb(n-1) + climb(n-2);;
}
int climbStairs(int n) {
    for(int i = 0; i < 46; i++) {
        men[i] = -1;
    }
    return climb(n);
}

2.2.3 动态规划

int climbStairs(int n) {
    int climb[46];
    climb[0] = 1;
    climb[1] = 2;

    for(int i = 2; i < n; i++) {
        climb[i] = climb[i-1] + climb[i-2];
    }

    return climb[n-1];
}

2.2.4 动态规划空间优化

int climbStairs(int n) {
    if(n <= 2) {
        return n;
    } else {
        int a = 1;
        int b = 2;
        int c = 0;
        while(n > 2) {
            c = a + b;
            a = b;
            b = c;
            --n;
        }
        return c;
    }
}

3. 结语

请给自己些耐心，不要急于求成。
山外青山楼外楼，莫把百尺当尽头。
保持空杯心态加油努力吧！

都看到这里啦！真棒(*^▽^*)

可以给作者一个免费的赞赞吗，这将会鼓励我继续创作，谢谢大家

编程小白写作，如有纰漏或错误，欢迎指正