DP入門之斐波那契數
斐波那契數，通常用 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);
- }
- };
- 時間復雜度：
- 空間復雜度：，算上了編程語言中實現遞歸的系統棧所占空間
這個遞歸的時間復雜度大家畫一下樹形圖就知道了，如果不清晰的同學，可以看這篇：通過一道面試題目，講一講遞歸算法的時間復雜度!
總結
斐波那契數列這道題目是非常基礎的題目，我在后面的動態規劃的講解中將會多次提到斐波那契數列!
這里我嚴格按照關于動態規劃，你該了解這些!中的動規五部曲來分析了這道題目，一些分析步驟可能同學感覺沒有必要搞的這么復雜，代碼其實上來就可以擼出來。
但我還是強調一下，簡單題是用來掌握方法論的，動規五部曲將在接下來的動態規劃講解中發揮重要作用，敬請期待!
本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。
