《剑指offer》 第10题扩展 变态跳台阶

一共n阶台阶，而青蛙的一步是从1到n都可以选择。

思路：虽然解的结果不是斐波那契数列，但是需要能观察出：
青蛙第一次可以跳1级，则还剩n - 1级台阶，即F(n - 1)
青蛙第一次可以跳2级，则还剩n - 2级台阶，即F(n - 2)
...
青蛙第一次可以跳n - 1级，则还剩1级台阶，即F(1)
青蛙第一次可以跳n级，即1种跳法
则F(n) = F(n - 1) + F(n - 2) + F(n - 3) + F(n - 4) + ... + F(1) + 1
而F(n-1) = F(n - 2) + F(n - 3) + F(n - 4) + F(n - 5) + ... + F(1) + 1
可以得到F(n) = 2 * F(n-1)

解法1：直接调用递归

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

解法2：考虑到F(n) = 2 * F(n-1) 实际是求2^(n-1)，因此也可以用位运算 返回一个需要求的幂就可以了。

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

解法3 使用数组记录计算过的值

public class Solution {
    public int JumpFloorII(int target) {
          if(target<=0 || target==1)
            return target;
        int[] arr =new int[target+1];
        arr[1]=1;
        for(int i=2;i<=target;i++){
            arr[i]=2*arr[i-1];
        }       
        return arr[target];
    }
}