变态跳台阶

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

思路：f(n)表示跳上一个n级的台阶的跳法，但每一次跳的台阶数不超过n

​ f(1) = f(1-1) 表示第一次跳一级台阶，剩下f(1-1)

​ f(2) = f(2-1)+f(2-2) 表示第一次跳一级台阶，剩下f(2-1),或第一次跳2级台阶，剩下f(2-2)

​ f(3) = f(3-1)+f(3-2)+f(3-3) 同上

​ ...

​ f(n-1) = f((n-1)-1)+f((n-1)-2)+....+f((n-1)-(n-2))+f((n-1)-(n-1)) = f(0)+f(1)+...+f(n-2)

​ f(n) = f(n-1)+f(n-2)+....+f(n-(n-1))+f(n-n) = f(0)+f(1)+...+f(n-2)+f(n-1)

​ 所以f(n) = 2 * f(n-1)

​ 得出递推式：

代码：

public int JumpFloorII(int n) {
    if(n == 0){
        return 0;
    }else if(n == 1) {
        return 1;
    }else{
        return 2*JumpFloorII(n-1);
    }
}