剑指offer题目9：变态跳台阶

/**

• 题目9：变态跳台阶
• 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
• /

//解法1：递归破解，时间、空间复杂度O(n^n),O(1)[这里不太清楚]  24ms
public int sum_9=0;
public void jump_9(int target){
    if(target<=0){
        if(target==0) sum_9++;
        return;
    }
    for(int i=1;i<=target;i++)
        jump_9(target-i);
}

//解法1的简化版       19ms
public int jump_9_simple(int target){
    if(target==0) return 1;
    int cnt=0;
    for(int i=0;i<target;i++)
        cnt+=jump_9_simple(i);
    return cnt;
}

/**解法2：利用公式，时间、空间复杂度O(n)、O(1)     16ms
 * 设跳第n阶梯的跳法数量是F(n)，那么F(n)=1+F(n-1)+F(n-2)+...+F(1)=2F(n-1)=2^(n-1)
 */
public int jump_9_2(int target){
    return 1<<(target-1);
}

/**
 * 解法3：动态规划，时间、空间复杂度O(n^2)、O(n)     16ms
 * （1）第n个状态都包含直接跳到第n步的跳法（0另外做讨论）
 * （2）第n个状态是前n-1种状态+直接跳n步的方法
 */
public int jump_9_3(int target){
    int [] res=new int[target+1];
    Arrays.fill(res,1);
    res[0]=0;
    for(int i=2;i<=target;i++){
        for(int j=i-1;j>=1;j--) res[i]+=res[j];
    }
    return res[target];
}