题解 | #跳台阶#

第四十一题 

方法一 正常的递归调用 并保存结果

class Solution {
public:
    // 记录已经被计算出来的值
    map<int,int> map_flag;
    int jumpFloor(int number) {
        // 递归 首先number=40，就是跳一个和跳两个的递归 递归调用jumpFloor(39 和 38)
        // 动态规划 的含义是保存之前计算过的结果。因为递归调用的时候，很多结果是会被重复调用的。
        // 最简单来说，当number是40，需要知道递归结果39 和 38
        // 那么当 number是39，又需要知道38 和 37，其中38是计算过的，所以应该提前保存下来。
        // 初始两个台阶的结果 也是递归结束的条件
        if(number<=1)
            return 1;
        if(map_flag.count(number))
            // 如果已经被计算过，直接获取计算的结果 而不用全部重新递归调用
            return map_flag[number];
        
        // 如果还没有调用过，更新最后计算到的结果，并将结果保存到map当中
        map_flag[number]=jumpFloor(number-1)+jumpFloor(number-2);
        return map_flag[number];
    }
};

方法二 非递归 从低层加到高层

class Solution {
public:
    int jumpFloor(int number) {
        // 方法二 还是动态规划 但是是非递归，从第一层开始 加到number层
        if(number == 1)
            return 1;
        int *dp=new int[number];
        dp[0]=1;
        dp[1]=2;
        // 非递归向后直接计算
        // 第三层的答案就是第1层+第2层的种类
        // 第四层的结果就是第3层+第2层...
        // 直到访问到number层结束！
        for(int i =2;i<number;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[number-1];
    }
};