跳台阶算法(变态版)

跳台阶算法(变态版)

题目描述:一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    /*
    * 思路:第一次跳,可以跳1 ,2 , 3, 4 , 5, 6, 7 ...n 个台阶
    * 跳1级,剩下的方法次数是f(n-1)
    * 跳2级,剩下的是f(n-2)
    * 所以 f(n) = f(1)+f(2)+f(3)+...f(n-1)
    * f(n-1) = f(1)+f(2)+...f(n-2)
    * f(n)  = 2 * f(n-1)
    * f(n -1 ) = 2 * f(n -2 )
    * 所以 f(n) = 2^n-1 f(1)
    * f(1) = 1
    * 得:f(n) = 2 ^ n-1
    * */
    public int JumpFloorII(int target) {
        return 1<< (target-1);
    }