斐波那契數(shù)是一個很好的熟悉和理解動態(tài)規(guī)劃的例子，通過斐波那契數(shù)可以更好的理解動態(tài)規(guī)劃的精髓，動態(tài)規(guī)劃是后面的計算是如何借助于前面的計算結(jié)果來加快計算速度的。
斐波那契數(shù)和斐波那契數(shù)列其實(shí)可以看成是一道題，只不過兩題的限制性條件稍微有差別
1 斐波那契數(shù)
1.1 斐波那契數(shù)
斐波那契數(shù) （通常用 F(n) 表示）形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始，后面的每一項數(shù)字都是前面兩項數(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.2.1 示例 1：
輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1
1.2.2 示例 2：
輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2
1.2.3 示例 3：
輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3
1.2.4 提示：
0 <= n <= 30
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/fibonacci-number
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
# 1.3 解題思路和方法
1.3.1 解題思路
如題目所說的，斐波那契數(shù)是最終是要獲得f[n]的斐波那契數(shù)。
其算法轉(zhuǎn)換方程如下：
F(0) = 0，F(xiàn)(1) = 1 /* 動態(tài)規(guī)劃的邊界條件 /
F(n) = F(n - 1) + F(n - 2)，其中 n > 1 / 動態(tài)規(guī)劃的轉(zhuǎn)移方程 */
1.3.2 代碼實(shí)現(xiàn)
- if (n < 2) 判斷當(dāng)前要處理的斐波那契數(shù)的id，依次來判斷是做什么處理，如果是小于2，則直接依據(jù)邊界條件的處理返回其值即可
- 如果n >= 2，則依據(jù)斐波那契數(shù)的轉(zhuǎn)換方程去做處理 F(n) = F(n - 1) + F(n - 2)
class Solution {
public:
int fib(int n) {
if (n < 2) {
return n;
}
vector<int> f(n + 1);
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
};
2 劍指 Offer 10- I. 斐波那契數(shù)列
2.1 斐波那契數(shù)列
寫一個函數(shù)，輸入 n ，求斐波那契（Fibonacci）數(shù)列的第 n 項（即 F(N)）。斐波那契數(shù)列的定義如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數(shù)列由 0 和 1 開始，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出。
答案需要取模 1e9+7（1000000007），如計算初始結(jié)果為：1000000008，請返回 1。
2.2 示例
2.2.1 示例 1：
輸入：n = 2
輸出：1
2.2.2 示例 2：
輸入：n = 5
輸出：5文章來源：http://www.zghlxwxcb.cn/news/detail-624774.html
2.2.3 提示：
0 <= n <= 100文章來源地址http://www.zghlxwxcb.cn/news/detail-624774.html
2.3 題解
class Solution {
int MOD = 1000000007;
public:
int fib(int n) {
if (n < 2) {
return n;
}
vector<int> f(n + 1);
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = (f[i - 1] + f[i - 2])%MOD;
}
return f[n];
}
};
到了這里，關(guān)于動態(tài)規(guī)劃-斐波那契數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
