【leetcode】青蛙跳楼梯问题

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

分析：设跳上第n个台阶的跳法为f(n),那么倒过来想，跳上第n个台阶的方法有：先跳上第n-1个台阶，然后再跳1个台阶到第n个台阶、先跳上第n-2个台阶，然后再直接跳到第n个台阶、先跳上第n-3个台阶，然后再直接跳到第n个台阶等等。如此有：
f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(1)
不要想着先跳到n-2个台阶再跳两下到最后台阶这样，因为这样的话已经包括在f(n-1)中了，所以上面这个式子已经全了。
同理，f(n-1)=f(n-2)+f(n-3)+…f(1)
可得递推公式： f(n)=2*f(n-1)
然后就简单了，f(1)=1为递推入口，最终代码如下：

class Solution {
public:
int jumpFloorII(int number) {
if(number0)
return 0;
else if(number1)
return 1;
else
return 2*jumpFloorII(number-1);
}
};