变态跳台阶

1.递归

f(n)=f(n-1)+f(n-2)+...+f(1)+1;
f(n-1)=f(n-2)+···+f(1)+1;
将下式带入上式，得到f(n)=2*f(n-1)

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

时间复杂度

2.循环解决

public class Solution {
    public int JumpFloorII(int target) {
       int ans = 1;
       for(int i = 1; i < target;i++){
           ans *= 2;
       }
        return ans;
    }
}

3.移位解决

public class Solution {
    public int JumpFloorII(int target) {
        return 1<<(target-1);
    }
}