JZ09-变态跳台阶

class Solution {

    //递推公式+递归 f(n) = 2 * f(n-1)
    public int JumpFloorII(int target) {
        if(target<0){
            return -1;
        }
        if(target <= 2){
            return target;
        }
        return 2*JumpFloorII(target - 1);
    }

    //递推公式 + 变量
    public int JumpFloorII2(int target) {
        if(target<0){
            return -1;
        }
        if(target <= 2){
            return target;
        }
        int b = 0;
        int a = 2;
        for (int i = 2; i < target; i++) {
            b = a << 1;
            a = b;
        }
        return b;
    }

    //动态规划。开辟数组
    public int JumpFloorII4(int target) {
        if (target < 0) {
            return -1;
        }

        if (target <= 2) {  //测试用例如果输入1，2直接返回
            return target;
        }

        int[] temp = new int[target + 1];
        temp[0] = 1;  //0个台阶，可以跳0阶 也算一种情况
        temp[1] = 1;
        temp[2] = 2;
        for (int i = 3; i <= target; i++) {
            for (int j = 0; j < i; j++) {
                temp[i] += temp[j]; //把i前面的全加起来等于i
            }
        }
        return temp[target];  //0-target 数组长度为target+1
    }

    //利用数组
    public int JumpFloorII3(int target) {
        if(target<0){
            return -1;
        }
        if(target <= 2){
            return target;
        }
        int b = 0;
        int a = 2;
        for (int i = 2; i < target; i++) {
            b = a << 1;
            a = b;
        }
        return b;
    }
}