跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

一、递归实现：

这种方法最为低级，递归会产生大量的重复计算，耗费的时间是输入规模的指数级别的，可以加入计算缓存来提高递归速度。

public class Solution {
    public int JumpFloor(int target) {
       if(target <=0 ) return 0;
       else if(target ==1 ) return 1;
       else if(target ==2 ) return 2;
       return JumpFloor(target-1)+JumpFloor(target-2);
    }
}

显然，当我们需要求jumpFloor(5)的时候，会计算jumpFloor(3)和jumpFloor(4)，为了得到jumpFloor(3)我们会计算jumpFloor(2)和jumpfloor(1),同样的，为了得到jumpfloor(4)，又会计算jumpFloor(3)，jumpFloor(2)和jumpfloor(1)，这样就会有大量的重复计算产生。

为了避免这种重复计算，最为直接的想法就是将这些中间步骤的计算结果保存下来，再下一次使用时直接进行取用。

二、动态规划：

记忆性动态规划 【递归】

根据如上思路，我们将中间步骤的结果保存下来，形成了记忆性的动态规划。
自底向上，保留每一步的运行结果，留待后续的使用。

public class Solution {
    public int JumpFloor(int target) {
       if(target <=0 ) return 0;
       if(target ==1 ) return 1;
       int[] dp = new int[target+1]; //从0到n一共长n+1
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=target;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[target];
    }
}

这样节省了时间，但也并不是完美的，因为递归的计算每一步的结果并保存，必然需要大量的空间，故而这种算法的时间复杂度是O(N),空间复杂度也是O(n)，在使用大量堆栈的情况下，容易造成栈溢出。

故而我们考虑将递归转化为递推求解。从底层向上一步步递推求解，并且为了优化空间利用率，我们并不需要把中间每一步的结果都保存，只需要保存前两步的结果来计算该层的结果。

空间优化后的递推型动态规划

根据如上思路，代码为：

public class Solution {
    public int JumpFloor(int target) {
       if(target <=0 ) return 0;
       if(target ==1 ) return 1;
        if(target ==2 ) return 2;
        int pre1 =1;
        int pre2=2;
        int result = 0;
        for(int i=3;i<=target;i++){
            result = pre1+pre2;
            pre1=pre2;
            pre2 = result;
        }
        return result;
    }
}

转为为递推后，不需要保存所有的中间结果，额外空间的使用为常数个空间，故而这种方法下，时间复杂度为O(N)，而空间复杂度为O(1)。

小结：

使用动态规划的时候，一定要先确定一些边界值的状态，然后再求出递归或递推公式。
另外，做一道题目一定要将它想透彻，这样才能达到做题的目的。