剑指Offer_8

发表于 | 分类于

题目

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

解题思路

找规律（斐波那契数列的应用）

a. 假设第一次跳1阶，那么剩下的跳法为f(n-1)
b. 假设第一次跳2阶，那么剩下的跳法为f(n-2)
c. 结合a,b考虑来看，总跳法为f(n) = f(n-1) + f(n-2)
d. 并且当n <= 2时, 跳法为n

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