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 递归
-
首先,函数判断如果 n 小于等于 2,则直接返回 n。因为在楼梯阶数小于等于 2 的情况下,只有一种方式爬到顶部,即分别走一步或者直接跨两步。
-
对于大于 2 的情况,函数采用递归的方式进行计算。爬到第 n 阶楼梯的方式数量等于爬到第 n-1 阶和第 n-2 阶的方式数量之和。这是因为爬到第 n 阶楼梯只有两种方式,一种是从第 n-1 阶再爬一阶,另一种是从第 n-2 阶再跨两阶。
-
最后,将计算得到的方式数量 sum 返回。
递归代码
int climbStairs(int n) {
if(2 >= n) {
return n;
}
int sum = 0;
sum = climbStairs(n-1) + climbStairs(n-2);
return sum;
}
2.1.2 记忆化搜索
- 首先,定义一个全局数组 men,大小为 46(因为题目中规定楼梯数不超过 45)。这个数组用来保存已经计算过的楼梯阶数对应的爬楼梯方式数量,避免重复计算。
- 接下来定义一个递归函数 climb(int n),用来计算爬到第 n 阶楼梯的方式数量。如果 n 小于等于 2,则直接返回 n,表示只有一种或两种方式爬到顶部。
- 如果 men[n] 不为 -1,说明之前已经计算过爬到第 n 阶楼梯的方式数量,直接返回 men[n]。
- 如果 men[n] 为 -1,说明还没有计算过爬到第 n 阶楼梯的方式数量,此时调用递归函数 climb(n-1) + climb(n-2) 来计算,并将结果保存在 men[n] 中,然后返回该结果。
- 最后,在 climbStairs 函数中,将 men 数组初始化为 -1,并调用 climb 函数来求解爬楼梯问题。
记忆化搜索代码
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.1.3 动态规划
- 首先,定义一个长度为 46 的整型数组 climb,用来存储爬到每个楼梯阶数的方式数量。数组初始化为 [1, 2],表示爬到第一阶和第二阶楼梯的方式数量分别为 1 和 2。
- 接下来,使用一个循环从第三阶楼梯开始计算爬楼梯的方式数量。对于第 i 阶楼梯,爬到这一阶的方式数量等于爬到第 i-1 阶和第 i-2 阶的方式数量之和,因为只有两种方式可以到达第 i 阶楼梯,要么是从第 i-1 阶跨一步,要么是从第 i-2 阶跨两步。
- 最后,返回数组 climb 中第 n-1 个元素,即爬到第 n 阶楼梯的方式数量。
动态规划代码
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.1.4 动态规划空间优化
- 如果输入的楼梯阶数 n 小于等于 2,那么直接返回 n,因为在这种情况下,只有一阶或者两阶楼梯,爬到顶部的方式数量分别为 1 和 2。
- 对于大于 2 的情况,定义三个变量 a、b 和 c,分别表示爬到第 n-2、第 n-1 和第 n 阶楼梯的方式数量。初始时,a 被赋值为 1(表示爬到第一阶楼梯的方式数量),b 被赋值为 2(表示爬到第二阶楼梯的方式数量)。
- 使用一个循环来计算爬到第 n 阶楼梯的方式数量。循环从第 3 阶楼梯开始,依次计算爬到每一阶楼梯的方式数量,直到计算到第 n 阶为止。
- 在循环中,更新 c 的值为 a + b,然后将 b 的值赋给 a,将 c 的值赋给 b,以便继续下一轮循环。
- 循环结束后,c 中存储的就是爬到第 n 阶楼梯的方式数量。
- 最后,返回 c。
动态规划空间优化代码
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;
}
}