变态跳台阶

public class Solution {
    public int JumpFloorII(int target) {
//         O(n^2)
         if(target==0)return 1;
         int sum=0;
         for(int i=1;i<=target;++i){
             sum+=JumpFloorII(target-i);
         }
         return sum;

//         O(n)
//         第n级台阶可以从第1~n-1级上来，即第n级的跳法是前面1~n-1级跳法之和
//         设f(n)=f(n-1)+f(n-2)+...f(1);
//         设f(n+1)=f(n)+f(n-1)+f(n-2)+...f(1);
//         两式相减 变换 得f(n+1)=2(fn);
//         当n>1时，f(n)=f(n-1);
         if(target<=1)return 1;
         else{
             return 2*JumpFloorII(target-1);
         }

//         O(1)进阶f(n)=2f(n-1)=2*2f(n-2)...2^(n-1)*f(1);
        return 1<<(target-1);
    }

}