目录
题目
假设你正在爬楼梯。需要 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
解答过程
递归方法很简单可以想到。首先要列出关系式:
f(1)=1,f(2)=2
f(n)=f(n-1)+f(n-2) n≥3
公式解释：如果只有一阶台阶，只有一种走法。如果两阶台阶，有1+1和2两种走法。有3种及以上个台阶，那么分以下两种情况，将两者进行相加，即为最终结果。
- 当你第一步走一个台阶，剩余的是f(n-1)种走法
- 当你第一步走两个台阶，剩余的是f(n-2)种走法
非循环方法：
方法一：就是利用两个变量循环进行保存前一个结果pre，和前面第二个结果prePre。还需要一个变量用来记录结果result。遍历内部核心部分代码如下：
result=pre+prePre;
prePre=pre;
pre=result;
方法二：使用哈希表进行存储所有的结果。
hashmap[i]=hashmap[i-1]+hashmap[i-2];
补充哈希表知识
unordered_map 是 C++ STL 中的关联容器，基于哈希表实现，提供快速的键值对查找功能。
哈希表基本特性
存储键值对（key-value pairs）
基于哈希表实现，平均情况下查找、插入、删除操作的时间复杂度为 O(1)
元素无序存储（与
map的有序存储相对）需要包含头文件
<unordered_map>
常用成员函数
insert(): 插入键值对erase(): 删除元素find(): 查找元素count(): 统计特定键的数量（0或1，因为键唯一）size(): 返回元素数量empty(): 判断是否为空clear(): 清空容器
基本用法
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// 创建 unordered_map
std::unordered_map<std::string, int> ageMap;
// 插入元素
ageMap["Alice"] = 25;
ageMap["Bob"] = 30;
ageMap.insert({"Charlie", 28});
// 访问元素
std::cout << "Alice's age: " << ageMap["Alice"] << std::endl;
// 检查元素是否存在
if (ageMap.find("David") == ageMap.end()) {
std::cout << "David not found" << std::endl;
}
// 遍历元素
for (const auto& pair : ageMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 删除元素
ageMap.erase("Bob");
return 0;
}实现代码
1.递归
class Solution {
public:
int climbStairs(int n) {
if (n==1)return 1;
if(n==2)return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
};但是递归方法会显示超出时间限制，提交会失败
2.循环遍历
class Solution {
public:
int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
int result=0;
int prePre=1;
int pre=2;
for(int i=3;i<=n;i++){
result=pre+prePre;
prePre=pre;
pre=result;
}
return result;
}
};3.哈希表
class Solution {
public:
int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
unordered_map<int,int> hashmap;
hashmap[1]=1;
hashmap[2]=2;
for(int i=3;i<=n;i++){
hashmap[i]=hashmap[i-1]+hashmap[i-2];
}
return hashmap[n];
}
};