1、題目描述

寫一個函數，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項（即 F(N)）。斐波那契數列的定義如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數列由 0 和 1 開始，之后的斐波那契數就是由之前的兩數相加而得出。
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。
示例 1：
輸入：n = 2
輸出：1
示例 2：
輸入：n = 5
輸出：5

2、VS2019上運行

代碼隨想錄的五步曲

#include <iostream>
#include <vector>class Solution {
public:int fib(int N) {if (N <= 1) return N;std::vector<int> dp(N + 1); // 創建一個長度為 N+1 的動態數組 dpdp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {dp[i] = dp[i - 1] + dp[i - 2]; // 計算斐波那契數列第 i 項的值}return dp[N]; // 返回斐波那契數列第 N 項的值}
};int main() {int N = 5;Solution s;int result = s.fib(N); // 調用 fib 方法計算斐波那契數列第 N 項的值std::cout << "Fibonacci number at position " << N << " is: " << result << std::endl;return 0;
}

運行結果：
Fibonacci number at position 5 is: 5
（這里出問題了，N=45時就出現錯誤，這是因為對于斐波那契數列，隨著 n 的增加，數列的值增長非常迅速。當使用普通的整數類型（如 int 或 long long）進行計算時，這些類型的取值范圍是有限的，無法容納較大的斐波那契數列項。）

換官方題解

#include <iostream>class Solution {
public:int fib(int n) {int MOD = 1000000007;  // 定義一個常量 MOD，用于取模運算if (n < 2) {return n;  // 如果 n 小于 2，直接返回 n 的值，因為斐波那契數列的前兩項是 0 和 1}int p = 0, q = 0, r = 1;  // 初始化前兩項和當前項的值for (int i = 2; i <= n; ++i) {p = q;  // 將 q 的值賦給 p，保留前一個項的值q = r;  // 將 r 的值賦給 q，更新當前項的值r = (p + q) % MOD;  // 計算下一項的值，并對 MOD 取模以避免溢出}return r;  // 返回斐波那契數列第 n 項的值}
};int main() {int N = 10;Solution s;  // 創建 Solution 類的對象int result = s.fib(N);  // 調用 fib 方法計算斐波那契數列第 N 項的值std::cout << "Fibonacci number at position " << N << " is: " << result << std::endl;return 0;
}

運行結果：
Fibonacci number at position 10 is: 55

3、代碼隨想錄解題思路

代碼隨想錄的動態規劃五步曲

• 1、確定dp數組（dp table）以及下標的含義
• 2、確定遞推公式
• 3、dp數組如何初始化
• 4、確定遍歷順序
• 5、舉例推導dp數組

4、官方題解解題思路

• 1.首先，我們定義了一個類 Solution，其中包含一個名為 fib 的方法，用于計算斐波那契數列的第 N 項的值。
• 2.在 fib 方法中，我們首先定義了一個常量 MOD，用于進行取模運算。這個常量的值是 1000000007，是為了在計算過程中避免溢出。
• 3.接下來，我們使用一個條件語句判斷給定的 n 是否小于 2。如果是，則直接返回 n 的值，因為斐波那契數列的前兩項是 0 和 1，所以它們的值與 n 相等。
• 4.然后，我們初始化三個變量 p、q 和 r 分別為 0、0 和 1。這些變量分別表示當前項、前一項和下一項的值。
• 5.進入循環，從索引 2 開始，直到 n。在每次循環中，我們更新變量的值：將 q 的值賦給 p，r 的值賦給 q，并計算 (p + q) % MOD 的結果并賦給 r。這樣就實現了逐步計算斐波那契數列的下一項的值。
• 6.循環結束后，我們返回變量 r 的值作為斐波那契數列的第 N 項的結果。