题解 | #跳台阶#

题解一:记忆化搜索
假设有n阶台阶，在所有的跳法中，由于青蛙一次只能跳1步或者2步，所以青蛙跳上最后一阶只能由f(n-1)+1 或者f(n-2)+2 这两种情况得来。
即：f(n)=f(n-1)+f(n-2)
同理:f(n-1)=f(n-2)+f(n-3),以此类推。
这其实就是一个斐波拉契数列。
图示如下：

根据思路我们可以实现递归代码：

class Solution {
public:
    int jumpFloor(int number) {
        if(number<=1) return 1;
        return  jumpFloor(number-1)+jumpFloor(number-2);
    }
};

仔细观察上图，可以发现，f(2)计算了两次，f(1)计算了3次，f(0)计算了2次。可以采用一个map存储已经被计算过的值(不采用vector的原因，不确定台阶的数量，无法预先申请确定大小的数组)。
具体实现如下：

class Solution {
public:
    map<int,int> map_flag;//记录已经被计算出来的值
    int jumpFloor(int number) {
        if(number<=1) return 1;//初始两个台阶的结果
        if(map_flag.count(number)){//已经被计算过;采用count的函数可以降低内存与时间；
            return map_flag[number];
        }
        return  map_flag[number]=jumpFloor(number-1)+jumpFloor(number-2);//未被计算过，存入map;
    }
};

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

题解二：动态规划
将记忆化搜索的递归部分修改为迭代。
1、题解一分析出本题f(n)可以拆分出重叠子问题f(n-1)、f(n-2);
2、f(n)=f(n-1)+f(n-2)是动态规划的状态转移方程；
3、f(0)=1,f(1)=1是动态规划的初始状态；
4、dp为一维数组，其中dp[i]的值代表青蛙跳第n个台阶的方法数；

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n),建立一个保存状态的数组;

实现如下:

class Solution {
public:

    int jumpFloor(int number) {
        vector<int> dp(number+1, 0);
        dp[0] = dp[1] = 1;//初始状态
        for (int i=2; i<=number; ++i) {
            dp[i] = dp[i-1] + dp[i-2];//状态转移方程
        }
        return dp[number];
    }
};

动态规划优化：状态压缩
我们可以看出：
1、在计算f(3)之后的值时,f(0)再也用不上了，没有必要保存；
2、每一个状态计算直接相关的只有当前值的前2个值；
那么我们可以只用两个值做保存前两个状态：

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)

实现如下：

class Solution {
public:
    int jumpFloor(int number) {
        if(number<=1)return 1;//初始两个台阶的结果
        int l1=1,l2=1;//用来保留前两次台阶的方法数
        for(int i=2;i<=number;++i){
            int temp=l1+l2;
            l1=l2;
            l2=temp;
        }
        return l2;
    }
};

相关题目:
斐波那契数列
矩形覆盖