题目描述:
· 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路:
由题意,可得:
青蛙跳上第n层台阶的跳法=青蛙跳上第n-1层台阶的跳法+青蛙跳上第n-2层台阶的跳法
即:
f(n)=f(n-1)+f(n-2)
是不是有点眼熟,本质就是 「斐波那契数列」(解法见[剑指offer][07]斐波那契数列)
代码实现:
class Solution {
public:
int jumpFloor(int number) {
//本质为斐波那契数列
if(number==0||number==1){
return 1;
}
int step1,step2,res;
step1=1;
step2=1;
res=1;
for(int i=2;i<=number;i++){
res=step1+step2;
step1=step2;
step2=res;
}
return res;
}
};