[剑指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);
    }
}