剑指offer

Problem

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

Solution

第n级台阶只能由第n-1阶台阶或第n-2阶台阶跳上来,所以这是一个斐波那契数列问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class 
{
public:
int jumpFloor(int number)
{
if (number <= 2) {
return number;
}

int prev1, prev2, sum;
prev1 = 1;
prev2 = 2;
sum = 0;

for (int i = 3; i <= number; ++i)
{
sum = prev1 + prev2;
prev1 = prev2;
prev2 = sum;
}

return sum;
}
};