LeetCode 热题 100_爬楼梯（81_70_简单_C++）
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入输出样例：
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示：
1 <= n <= 45
题解：
解题思路：
思路一（动态规划）：
1、这道题最主要的是分析出怎么解决爬楼梯，能否找到一定的规律。们发现,当我们爬第n层台阶的时候可以从n-1层台阶或n-2层台阶爬上来。
① 当楼梯数n=1时 有1种方法：1
② 当楼梯数n=2时 有2种方法：1+1，2
③ 当楼梯数n=3时 有3种方法：1+1+1，2+1;1+2。可以转换成从n=1爬2个台阶上来，和n=2爬1层台阶上来。
④ 当楼梯数n=4时 有5种方法：1+1+1+1，2+1+1，1+2+1;1+1+2,2+2。可以转换成从n=2爬2个台阶上来，和n=3爬1层台阶上来。
⑤ 我们发现f(n)=f(n-1)+f(n-2),正好符合斐波那契数列。
2、复杂度分析：
① 时间复杂度：O(n)。从第一层爬到第n层。
② 空间复杂度：O(1)。
代码实现
代码实现（思路一（动态规划））：
class Solution {
public:
int climbStairs(int n) {
// 初始化：
// a = 1：表示爬到第 0 阶（地面）的方式数为 1
// b = 1：表示爬到第 1 阶的方式数为 1
// sum = 1：用于计算当前计算的阶梯方式数
int a = 1, b = 1, sum = 1;
// 循环直到 n 减少到 1
// 计算从第 2 阶到第 n 阶的方式数，依次更新 a 和 b 的值
while (n - 1) {
// sum 存储爬到当前阶数（第 n 阶）的方式数
// 当前阶数的方式数等于爬到前一阶（a）和前两阶（b）的方式数之和
sum = a + b;
// 更新 a 和 b：
// a 更新为 b，表示爬到第 n 阶的方式数
a = b;
// b 更新为 sum，表示爬到下一个阶数（第 n+1 阶）的方式数
b = sum;
// 每次循环将 n 减少 1，直到 n 为 1 时退出循环
--n;
}
// 返回 b，最终它存储的是爬到第 n 阶的方式数
return b;
}
};
以思路一为例进行调试
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int climbStairs(int n) {
// 初始化：
// a = 1：表示爬到第 0 阶（地面）的方式数为 1
// b = 1：表示爬到第 1 阶的方式数为 1
// sum = 1：用于计算当前计算的阶梯方式数
int a = 1, b = 1, sum = 1;
// 循环直到 n 减少到 1
// 计算从第 2 阶到第 n 阶的方式数，依次更新 a 和 b 的值
while (n - 1) {
// sum 存储爬到当前阶数（第 n 阶）的方式数
// 当前阶数的方式数等于爬到前一阶（a）和前两阶（b）的方式数之和
sum = a + b;
// 更新 a 和 b：
// a 更新为 b，表示爬到第 n 阶的方式数
a = b;
// b 更新为 sum，表示爬到下一个阶数（第 n+1 阶）的方式数
b = sum;
// 每次循环将 n 减少 1，直到 n 为 1 时退出循环
--n;
}
// 返回 b，最终它存储的是爬到第 n 阶的方式数
return b;
}
};
int main(){
Solution s;
cout<<s.climbStairs(7);
return 0;
}
LeetCode 热题 100_爬楼梯（81_70)原题链接
欢迎大家和我沟通交流(✿◠‿◠)