题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析一下明天是个斐波那契数列，我们一步一步退出其通项公式。
设台阶数为n， 总跳法为jumps
n jumps
1 1
2 2
3 4
4 8
5 16
现在猜测其通项公式为 fbonicc(n) = 2 * fbonicc(n - 1)
列出4的全部跳法 5的全部跳法
1111 1111 （1）
2 11 2 11 （1）
1 2 1 1 2 1 （1）
1 1 2 1 1 2（1）
2 2 2 2 （1）
1 3 1 3 （1）
3 1 3 1 （1）
4 4 （1）
111（1+1）
2 1 （1+1）
1 2 （1+1）
1 1 （2 + 1）
2 （2+1）
1 （3+1）
3 （1+1）
（4+1）
so 这次应该可以看出规律了！也就是fbonicc(n) = 2 * fbonicc(n - 1)
c++代码实现
递归实现
class Solution {
public:
int jumpFloorII(int number) {
if (number == 1) return 1;
else return 2 * jumpFloorII(number - 1);
}
};
非递归实现
class Solution {
public:
int jumpFloorII(int number) {
long long fibonicc = 1;
for (int i = 2;i <= number;i++)
fibonicc *= 2;
return fibonicc;
}
};
