跳台阶【Java版】

1）斐波拉切-O(N)动态规划

public class Solution {
    public int JumpFloor(int target) {
        int frog[]=new int[100];
        frog[1]=1;frog[2]=2;
        for (int i=3;i<=target;i++){
            frog[i]=frog[i-1]+frog[i-2];
        }
        return frog[target];
    }
}
//原理同：斐波那契数列
//【动态规划】时间O(N)，空间O(N)
//如果只要最后的结果，那么可以撤销数组，使用a/b/c三个变量存储即可。空间复杂度减为O(1)

2）空间O(1)的方法

public class Solution {
    public int jumpFloor(int target) {
        if(target<=2)return target;
        int lastOne = 2;  //现在位置上一个，相当于fi[i-1]
        int lastTwo = 1;  //相当于fi[i-2]
        int res = 0;
        for(int i=3; i<=target; ++i){
            res = lastOne + lastTwo;
            lastTwo = lastOne;
            lastOne = res;
        }
        return res;
    }
}
//这种方法的空间复杂度为：O(1)
//时间复杂度虽然也为O(N)，但是比上一种动态规划的方法耗时，因为循环里面操作较多
//相当于时间换空间，花费时间在不断倒腾地方