[剑指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为整数) 这就是斐波那契数列的变形，因此可以用递归来实现。

参考代码

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);
    }
}