LeetCode 热题 100_爬楼梯（81_70_简单

LeetCode 热题 100_爬楼梯（81_70_简单_C++）(动态规划)

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;
}