題目：斐波那契數(shù)列

題目描述：

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項(xiàng)。
n<=39

題目思考：

首先，我們需要知道的是斐波那契數(shù)列是什么？

image.png

既然我們知道了什么事斐波那契數(shù)列，那我們最先想到的方法就是通過數(shù)列的通項(xiàng)公式，通過遞歸的方式來計算n的對應(yīng)值F(n).

題目思路一：

最簡單最之際的方法，也是我們最先想到的，但是卻是最不推薦的，通過遞歸的方式，這種方式占用時間和內(nèi)存都不是最優(yōu)的。

class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 0) return 0;
        if(n == 1|| n == 2) return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
};

題目思路二：

題目思考中的方式，通過中間變量的，迭代循環(huán)，不斷疊加，最終計算出數(shù)據(jù)結(jié)果。

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        
        int temp1 = 0,temp2 = 1;
        int result = 0;
        for(int i = 2; i<= n; i++){
            result = temp1 + temp2;
            temp1 = temp2;
            temp2 = result;
        }
        return result;
    }
};

題目思路三：

在網(wǎng)上看的，動態(tài)規(guī)劃的方式，我自習(xí)看了一下，其實(shí)和遞歸循環(huán)的方式有些類似，唯一的差別就是將中間存貯結(jié)果的變量省略，通過兩個數(shù)據(jù)加減實(shí)現(xiàn)最終的這個算法。

方式一：
class Solution {
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while(n--){
            g =  g + f;
            f = g - f;
        }
        return f;
    }
};

方式二：
class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 0) return 0;
        int f = 0, g = 1;
        while(n-- > 1){
            g =  g + f;
            f = g - f;
        }
        return g;
    }
};

兩種方式的差別在于返回的是g還是f：
第一種代碼其實(shí)多循環(huán)了一次，最終的結(jié)果是n的下一階，所以我們沒有輸出g，而是輸出f。
第二種代碼就是正合適的循環(huán)次數(shù)，最終結(jié)果就是n，所以我們就輸出g，而不是輸出f。