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