剑指Offer算法题-青蛙跳台阶

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题解

这道题和斐波那契思想一毛一样，关于斐波那契数列的算法，这两篇文章已有详细阐述

两种斐波那契数列非递归算法（堆栈模拟、循环）

记忆化搜索--优化斐波那契数列递归函数

这里用map方式实现记忆化搜索

class Solution {
public:
    map<int, int> mp;
    int jumpFloor(int number) {
        if(number <= 2) return number;
        int ans;
        if(mp[number] != 0) ans = mp[number];
        else{
            ans = jumpFloor(number - 1) + jumpFloor(number - 2);
            mp[number] = ans;
        } 
        return ans;
    }
};