[[442531]]

斐波那契數(shù)，通常用 F(n) 表示，形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：F(0) = 0，F(xiàn)(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

思路

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

因?yàn)檫@道題目比較簡單，可能一些同學(xué)并不需要做什么分析，直接順手一寫就過了。

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

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

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

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

動態(tài)規(guī)劃

動規(guī)五部曲：

這里我們要用一個一維dp數(shù)組來保存遞歸的結(jié)果

1.確定dp數(shù)組以及下標(biāo)的含義

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

2.確定遞推公式

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

因?yàn)轭}目已經(jīng)把遞推公式直接給我們了：狀態(tài)轉(zhuǎn)移方程 dp[i] = dp[i - 1] + dp[i - 2];

3.dp數(shù)組如何初始化

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

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

4.確定遍歷順序

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

5.舉例推導(dǎo)dp數(shù)組

按照這個遞推公式dp[i] = dp[i - 1] + dp[i - 2]，我們來推導(dǎo)一下，當(dāng)N為10的時候，dp數(shù)組應(yīng)該是如下的數(shù)列：

0 1 1 2 3 5 8 13 21 34 55

如果代碼寫出來，發(fā)現(xiàn)結(jié)果不對，就把dp數(shù)組打印出來看看和我們推導(dǎo)的數(shù)列是不是一致的。

以上我們用動規(guī)的方法分析完了，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]; 
    } 
}; 

• 時間復(fù)雜度：
• 空間復(fù)雜度：

當(dāng)然可以發(fā)現(xiàn)，我們只需要維護(hù)兩個數(shù)值就可以了，不需要記錄整個序列。

代碼如下：

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]; 
    } 
}; 

• 時間復(fù)雜度：
• 空間復(fù)雜度：

遞歸解法

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

代碼如下：

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

• 時間復(fù)雜度：
• 空間復(fù)雜度：，算上了編程語言中實(shí)現(xiàn)遞歸的系統(tǒng)棧所占空間

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

總結(jié)

斐波那契數(shù)列這道題目是非?；A(chǔ)的題目，我在后面的動態(tài)規(guī)劃的講解中將會多次提到斐波那契數(shù)列!

這里我嚴(yán)格按照關(guān)于動態(tài)規(guī)劃，你該了解這些!中的動規(guī)五部曲來分析了這道題目，一些分析步驟可能同學(xué)感覺沒有必要搞的這么復(fù)雜，代碼其實(shí)上來就可以擼出來。

但我還是強(qiáng)調(diào)一下，簡單題是用來掌握方法論的，動規(guī)五部曲將在接下來的動態(tài)規(guī)劃講解中發(fā)揮重要作用，敬請期待!

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。