最近在刷一些數(shù)據(jù)結(jié)構(gòu)的題，發(fā)現(xiàn)個(gè)很有趣的問題：跳臺(tái)階問題。

1. 第一題（引子）：輸出菲波那切數(shù)列的第N項(xiàng)。

斐波那契數(shù)列含義（百度百科）：
指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F(0)=0，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

菲波那切數(shù)列是一個(gè)很有趣的數(shù)列，并且在很多的科研領(lǐng)域都是有應(yīng)用的（就不介紹有哪些應(yīng)用了，因?yàn)樘╳o）高（ye）深（bu）了（hui））。

那用程序怎么實(shí)現(xiàn)出來呢？首先根據(jù)定義：F(n)=F(n-1)+F(n-2) 作為程序員很容易想到可以使用遞歸來實(shí)現(xiàn)。沒錯(cuò)，下面是遞歸的實(shí)現(xiàn)：

    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if( n<=2 ){
            return 1;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);   
    }

很好理解吧，遞歸的出口就是n=0，n=1，n=2的時(shí)候

但是這種做法有什么問題呢？簡(jiǎn)單來說這種做法的遞歸的深度是在是太深了。舉個(gè)例子：
我們計(jì)算n為4的情況：那么我們需要做如下的計(jì)算：
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
看看，多做了多少計(jì)算。2 計(jì)算了 2次，1 計(jì)算了5次，0計(jì)算了3次。正常來說我們計(jì)算4次就可以了吧。這樣相當(dāng)于多做了4次。

那我們就像能不能用迭代的方式來，觀察下數(shù)列，想了下，感覺靠譜：

public static int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if( n<=2 ){
            return 1;
        }
        int i1 = 1;
        int i2 = 1;
        int count = 3;
        while (count++<=n) {
            int number = i1+i2;
            i1 = i2;
            i2 = number;
        }
        return i2;
    }

我們知道只需要把上次的計(jì)算的值用來作為這次計(jì)算了第一項(xiàng)值，來循環(huán)最后就求出了我們想要的第n項(xiàng)的值。

看到這你可能想問了：這和跳臺(tái)階有什么關(guān)系呢？不要著急來看下這個(gè)問題：

2. 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

想一想看一看，發(fā)現(xiàn)是不是有種似曾相識(shí)的感覺，可以把這個(gè)問題分解成：
如果兩種跳法，1階或者2階，那么假定第一次跳的是一階，那么剩下的是n-1個(gè)臺(tái)階，跳法是f(n-1);那么假定第一次跳的是2階，那么剩下的是n-2個(gè)臺(tái)階，跳法是f(n-2)。那總的問題是不是就變成了F(n)=F(n-1)+F(n-2)。呵呵，這不就是菲波那切數(shù)列嗎問題嗎（雖然不是完全一樣，前兩項(xiàng)變成了 1 2了）。代碼如下：

public static int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if( n<=2 ){
            return 1;
        }
        int i1 = 1;
        int i2 = 1;
        //只把這里改成2就可以了，以為這個(gè)序列不是 1 1 2 3 5....了，是 1 2 3 5.... 少了個(gè)1
        int count = 2;
        while (count++<=n) {
            int number = i1+i2;
            i1 = i2;
            i2 = number;
        }
        return i2;
    }

看到這里你可能會(huì)恍然大悟，大叫原來如此。但你再看下下面這個(gè)問題：

3. 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

如果你足夠聰明，大概已經(jīng)知道套路了，我們可以看下這個(gè)問題怎么分解成一個(gè)多項(xiàng)式：

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

分解完了然后怎么辦呢？我們第一個(gè)想法可能是用遞歸啊，一個(gè)for循環(huán)，然后在for循環(huán)里遞歸求每個(gè)子項(xiàng)，然后等n為0的時(shí)候返回1就可以了。

我想說這么做也可以但是你感覺是不是很惡心，這運(yùn)行起來?xiàng)５纳疃仁遣皇且苌盍恕?/p>

那我們觀察下，看能不能化簡(jiǎn)什么的。靈機(jī)一動(dòng)，發(fā)下好像可以：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

完美，這回在用遞歸次數(shù)就明顯下來了。
代碼如下：
```
public int JumpFloorII(int target) {
        if (target <= 1) {
            return 1;
        } else {
            return 2 * JumpFloorII(target - 1);
        }
    }
```

做到這里，咱們是不是自然的想到，我們可以不可以算下：
####4. 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)m級(jí)的臺(tái)階總共有多少種跳法。

這回我想大家應(yīng)該都會(huì)了這種套路了。我們先不說話，先列多項(xiàng)式：
f(n) =  f(n-1) + f(n-2) + f(n-3) + ... + f(n-m)
f(n-1) =   f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)
化簡(jiǎn)得：f(n) = 2f(n-1) - f(n-m-1)

OK，上代碼：
```
    public static int JumpFloorIII(int target,int m ) {
        //當(dāng)大于m的時(shí)候是上面的公式
        if(target > m){
            return 2*JumpFloorIII(target-1, m)-JumpFloorII(target-1-m, m);
        }
        //當(dāng)小于等于m的時(shí)候就是和n級(jí)的相同了
        if (target <= 1) {
            return 1;
        } else {
            return 2 * JumpFloorIII(target - 1,target);
        }
    }
```

完美~~~