[[442531]]

斐波那契數，通常用 F(n) 表示，形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 給你n ，請計算 F(n) 。

示例 1：

• 輸入：2
• 輸出：1
• 解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

• 輸入：3
• 輸出：2
• 解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

• 輸入：4
• 輸出：3
• 解釋：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

思路

斐波那契數列大家應該非常熟悉不過了，非常適合作為動規第一道題目來練練手。

因為這道題目比較簡單，可能一些同學并不需要做什么分析，直接順手一寫就過了。

但「代碼隨想錄」的風格是：簡單題目是用來加深對解題方法論的理解的。

通過這道題目讓大家可以初步認識到，按照動規五部曲是如何解題的。

對于動規，如果沒有方法論的話，可能簡單題目可以順手一寫就過，難一點就不知道如何下手了。

所以我總結的動規五部曲，是要用來貫穿整個動態規劃系列的，就像之前講過二叉樹系列的遞歸三部曲，回溯法系列的回溯三部曲一樣。后面慢慢大家就會體會到，動規五部曲方法的重要性。

動態規劃

動規五部曲：

這里我們要用一個一維dp數組來保存遞歸的結果

1.確定dp數組以及下標的含義

dp[i]的定義為：第i個數的斐波那契數值是dp[i]

2.確定遞推公式

為什么這是一道非常簡單的入門題目呢?

因為題目已經把遞推公式直接給我們了：狀態轉移方程 dp[i] = dp[i - 1] + dp[i - 2];

3.dp數組如何初始化

題目中把如何初始化也直接給我們了，如下：

dp[0] = 0; 
dp[1] = 1; 

4.確定遍歷順序

從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依賴 dp[i - 1] 和 dp[i - 2]，那么遍歷的順序一定是從前到后遍歷的

5.舉例推導dp數組

按照這個遞推公式dp[i] = dp[i - 1] + dp[i - 2]，我們來推導一下，當N為10的時候，dp數組應該是如下的數列：

0 1 1 2 3 5 8 13 21 34 55

如果代碼寫出來，發現結果不對，就把dp數組打印出來看看和我們推導的數列是不是一致的。

以上我們用動規的方法分析完了，C++代碼如下：

class Solution { 
public: 
    int fib(int N) { 
        if (N <= 1) return N; 
        vector<int> dp(N + 1); 
        dp[0] = 0; 
        dp[1] = 1; 
        for (int i = 2; i <= N; i++) { 
            dp[i] = dp[i - 1] + dp[i - 2]; 
        } 
        return dp[N]; 
    } 
}; 

• 時間復雜度：
• 空間復雜度：

當然可以發現，我們只需要維護兩個數值就可以了，不需要記錄整個序列。

代碼如下：

class Solution { 
public: 
    int fib(int N) { 
        if (N <= 1) return N; 
        int dp[2]; 
        dp[0] = 0; 
        dp[1] = 1; 
        for (int i = 2; i <= N; i++) { 
            int sum = dp[0] + dp[1]; 
            dp[0] = dp[1]; 
            dp[1] = sum; 
        } 
        return dp[1]; 
    } 
}; 

• 時間復雜度：
• 空間復雜度：

遞歸解法

本題還可以使用遞歸解法來做

代碼如下：

class Solution { 
public: 
    int fib(int N) { 
        if (N < 2) return N; 
        return fib(N - 1) + fib(N - 2); 
    } 
}; 

• 時間復雜度：
• 空間復雜度：，算上了編程語言中實現遞歸的系統棧所占空間

這個遞歸的時間復雜度大家畫一下樹形圖就知道了，如果不清晰的同學，可以看這篇：通過一道面試題目，講一講遞歸算法的時間復雜度!

總結

斐波那契數列這道題目是非常基礎的題目，我在后面的動態規劃的講解中將會多次提到斐波那契數列!

這里我嚴格按照關于動態規劃，你該了解這些!中的動規五部曲來分析了這道題目，一些分析步驟可能同學感覺沒有必要搞的這么復雜，代碼其實上來就可以擼出來。

但我還是強調一下，簡單題是用來掌握方法論的，動規五部曲將在接下來的動態規劃講解中發揮重要作用，敬請期待!

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。