2024.9.6 leetcode 70 爬楼梯 (哈希表/动态规划)

题面70. 爬楼梯 - 力扣（LeetCode）

题解：极其经典的一道动态规划，比如要跳到10楼有f(10）种方法，可以分为1、先跳到9楼再往上跳1楼 2、先跳到8楼再往上跳2楼，所以f(10)=f(8)+f(9)，昨天复习了哈希表，所以用哈希练习一下。

class Solution {
public:
    int climbStairs(int n) {
        unordered_map<int,int>  umap;
        umap.insert({1,1});
        umap.insert({2,2});
        for(int i=3; i <= 45; i++)
        {
            umap.insert({i,umap[i-1]+umap[i-2]});
        }
        return umap[n];
    }
};