[剑指offer] 跳台阶

题目描述

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

解题思路

按照题意,

1 级 —- 1 种

2 级 —- 2 种

3 级 —- 3 种

4 级 —- 5 种

5 级 —- 8 种

我们可以得到一种规律,如果要跳 6 级,可以从 5 级跳一步到 6 级,5 级的方案中有多少种就有多少种跳法跳到 6 级;还可以从 4 级跳两步到 6 级,同理,4 级的方案有多少种就有多少种方法从 4 级跳到 6 级,所以可以得到公式f(n) = f(n-1) + f(n-2),再结合 1 级和 2 级的情况,可以得以如下的规律:

f(n) = 1, (n=1)

f(n) = 2, (n=2)

f(n) = f(n-1)+f(n-2) ,(n>2,n为整数)

这就是斐波那契数列的变形,因此可以用递归来实现。

参考代码

1
2
3
4
5
6
7
8
9
10
public class Solution {
public int JumpFloor(int target) {
if(target<=0)
return 0;
else if(target == 1|| target == 2)
return target;
else
return JumpFloor(target-1)+JumpFloor(target-2);
}
}