凍龜算法系列之斐波那契數(shù)列模型
【動態(tài)規(guī)劃】斐波那契數(shù)列模型
動態(tài)規(guī)劃（英語：Dynamic programming，簡稱 DP），是一種在數(shù)學(xué)、管理科學(xué)、計算機科學(xué)、經(jīng)濟學(xué)和生物信息學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。
至于這個模型是什么意思，我覺得你往下看下去，自主感受那些相似之處，才不會懵逼~
而本文為動態(tài)規(guī)劃系列的第一篇，所以在動態(tài)規(guī)劃做題步驟上會比較分明，接下來的幾道例題，讓我們邊實戰(zhàn)邊學(xué)吧！
文章解題的大的流程為：
- 題目解析
- 算法原理（可能會有其他解法，在這個系列只講解動態(tài)規(guī)劃的思想）
- 編寫代碼
- 空間優(yōu)化
- 動態(tài)規(guī)劃一般很難，做出來已經(jīng)不錯了，所以主要重心放在解題上
- 本文第一道題，把所有流程都會過一遍，所以會講，而在講背包問題之前，都不會出現(xiàn)這個步驟
- 因為動態(tài)規(guī)劃一般會比較浪費空間，所以才有這個空間優(yōu)化的必要
1. 第N個泰波那契數(shù)
傳送門：力扣1137
題目：
1.1 題目解析
所以有以下示例：
同理：
1.2 算法原理
算法原理分析的過程分五步：
- 畫出dp表并確定dp表 狀態(tài)表示
- 根據(jù)狀態(tài)表示確定 狀態(tài)轉(zhuǎn)移方程
- 初始化 dp表
- 確定 填表順序
- 確定 返回值
由于是第一道題，所以下面是細致講解！
- 但是因為這道題比較簡單，一些方面沒有涉及到，但是對于初學(xué)者，這樣才最友好，因為本題重點就是熟悉做題流程！
- 在后續(xù)的學(xué)習中，反復(fù)積累經(jīng)驗，了解方方面面，再依此基礎(chǔ)上去刷題，才能學(xué)好動態(tài)規(guī)劃！
1.2.1 狀態(tài)表示
什么是狀態(tài)表示：
這就涉及動態(tài)規(guī)劃的核心：dp表
- 這個dp表的建立是不固定的，可能是一維數(shù)組，二維數(shù)組等等…
而dp表中的元素與其對應(yīng)下標有什么關(guān)系，即這個元素的**含義**，或者說是這個元素所處的“狀態(tài)”（抽象籠統(tǒng)的說法）
- 而其中，我們要的答案，就是dp表其中的一個元素
例子：
- 開心or不開心，是狀態(tài)
- 1下標元素的含義就是滑稽老鐵開心
- 當然，dp表代表的狀態(tài)一般不是對立的，而是這樣的
- 而之后我們可以 以“含義”去理解
而設(shè)立的狀態(tài)表示不一樣，也意味著思路不一樣，即不同的解法~
- 想到一個，然后就去試試能不能解…
- 做多點題，這一步準確率會高點~
怎么來？
- 經(jīng)驗 + 題目要求
- 分析問題的過程中，發(fā)現(xiàn)重復(fù)的子問題，抽象成狀態(tài)表示（暫時不講）
而這道題，我們只需建立一個一維dp表（大小為n + 1）：
- 題目要求：返回第n個泰波那契數(shù)的值
- 經(jīng)驗：dp[n]應(yīng)該就是答案
即dp[i]表示：第 i 個泰波那契數(shù)的值
1.2.2 狀態(tài)轉(zhuǎn)移方程
什么是**狀態(tài)轉(zhuǎn)移方程**：
- 就是，dp[i] = … ;
- 而這個方程可能有條件，分支，循環(huán)等復(fù)雜的邏輯…
而dp[i]是由dp表其他下標對應(yīng)的值來推導(dǎo)出來的
- 比如，dp[i]之前或者之后的值可以推出dp[i]
例子：
- 開心是會傳染的：
而本題的動態(tài)轉(zhuǎn)移方程就是：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
- 難的方程怎么推導(dǎo)？
- 遇到再說
- 現(xiàn)在紙上談兵沒有意義
對應(yīng)動態(tài)規(guī)劃的題目而言，前兩步是最最重要的，也就是百分之99已完成~
接下來就是一些細節(jié)的處理
1.2.3 初始化
- 很明顯，通過已知推未知的過程中，會遇到一些數(shù)組越界等問題…，而初始化就是為了解決這些問題
本題為：
- i - 1，i - 2，i - 3要有意義，則i要大于等于3
- 所以在初始化的時候，手動給dp[0]、dp[1]、dp[2]賦值（賦值之前要確保不越界，越界就直接返回即可）
1.2.4 填表順序
我們通過已知推未知，這里的已知可能是i之前或者i之后，這就分為了簡單的兩個大方向（一維dp表）
本題為：順序1
-
要保證填這個下標的時候，需要用到的其他下標，是已經(jīng)在此之前填了的！
- 即，計算過了的
1.2.5 返回值
根據(jù)題目要求 + 狀態(tài)表示得出返回值
本題為：dp[n]
- 注意下標確定是哪個
- 可以說返回值和狀態(tài)表示是同時確定的
1.3 編寫代碼
編寫代碼分為固定的四步：
- 創(chuàng)建dp表
- 初始化
- 算法主體（填表）
- 返回值
class Solution {
public int tribonacci(int n) {
//1. 創(chuàng)建dp表
int[] dp = new int[n + 1];
//2. 初始化
if(n == 0) {
return 0;
}
if(n == 1 || n == 2) {
return 1;
}
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
//3. 填表
for(int i = 3; i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
//4. 返回值
return dp[n];
}
}
- 由于我們要訪問到dp[n]并返回，所以dp表的大小為n + 1
- 初始化之前要進行判斷，否則會數(shù)組越界
- 通過狀態(tài)轉(zhuǎn)移方程來填表
- 返回dp[n]
在提交之前測試一下，可以自行輸入實例去測~
可見空間復(fù)雜度和時間復(fù)雜度都為O(N)
1.4 空間優(yōu)化
通過“滾動數(shù)組”去進行空間優(yōu)化
- O(N2) => O(N)
- O(N) => O(1)
算法修改思想：
- 計算dp[i]其實只需要用到dp[i - 1] + dp[i - 2] + dp[i - 3]，其實一直都是用三塊空間，所以我們只需要反復(fù)使用則三塊空間就行了
class Solution {
public int tribonacci(int n) {
//1. 空間優(yōu)化
int[] src = new int[3];
src[0] = 0;
src[1] = 1;
src[2] = 1;
//2. 初始化
if(n == 0) {
return 0;
}
if(n == 1 || n == 2) {
return 1;
}
int ret = 0;
//3. 填表
for(int i = 3; i < n + 1; i++) {
ret = src[0] + src[1] + src[2];
src[0] = src[1];
src[1] = src[2];
src[2] = ret;
}
//4. 返回值
return ret;
}
}
賦值操作則是這樣的：
則就從頭部挪，而不是從尾部挪
從頭部開始挪：
- 正常
從尾部開始挪：
- 異常，最終三個值都為2
第一道題就這樣愉快的結(jié)束了，想必你已經(jīng)了解了動態(tài)規(guī)劃作答的流程了，接下來就是做幾道題，走幾遍流程，好好感受它“動歸思想”~
2. 三步問題
傳送門：面試題08.01.
題目：
2.1 題目解析
- 小明一次可以跨1、2、3步~
輸入一個數(shù)n，求出從0到n的爬法數(shù)
通過示例探索規(guī)律：
-
并且結(jié)果要模上1e9 + 7！
- 1eN = 1.0 × 10N，所以這個值為浮點型
- 一般我們習慣定義一個int型常數(shù)DOM 等于這里的1eN；
- 這其實就是個科學(xué)計數(shù)法形式的浮點型罷了
2.2 算法原理
2.2.1 狀態(tài)表示
很顯然，這要用到一維的順序結(jié)構(gòu)，dp表的大小為n + 1
題目要求：
- 返回到達第n個臺階的爬法數(shù)
經(jīng)驗：以某個節(jié)點為結(jié)尾或者以某個節(jié)點為起點去研究問題
- 此題就是以第i個節(jié)點為結(jié)尾，用 i 之前的節(jié)點推導(dǎo)出第 i 個節(jié)點的值
- 結(jié)果應(yīng)該為dp[n]（dp表其中一值）
得出dp表元素dp[i]的含義就是，到達第 i 個臺階的爬法數(shù)
2.2.2 狀態(tài)轉(zhuǎn)移方程
而得出狀態(tài)轉(zhuǎn)移方程的思想就是：借用“已知”狀態(tài)！
- 我們就幻想dp[i]之前的值，是已知，則有以下操作
我們要到達 i，那么我們到達前的位置可以是：i - 1，i - 2，i - 3：
- 到達i - 1，有dp[i - 1]種爬法，然后跳三步到達 i
- 到達i - 2，有dp[i - 2]種爬法，然后跳兩步到達 i
- 到達i - 3，有dp[i - 3]種爬法，然后跳一步到達 i
到達i - 1可以跳兩步在跳一步或者跳一步再跳兩步之類的啊
- 沒錯，但是這包含在情況2和情況3中（到達i -2 或者 到達 i - 3）
所以得出dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
- 變成泰波那契數(shù)列了~
可以通過示例驗證一下想法：
2.2.3 初始化
同樣的，i - 3 、i - 2、i - 1 需要考慮數(shù)組越界的問題~
2.2.4 填表順序
dp[i]之前是已知，則填表應(yīng)從左到右~
2.2.5 返回值
返回dp[n]~
2.3 編寫代碼
一樣的，分為四步：
- 創(chuàng)建dp表
- 初始化
- 填表
- 返回值
class Solution {
public int waysToStep(int n) {
//1. 創(chuàng)建表
int[] dp = new int[n + 1];
int MOD = (int)1e9 + 7; //取模數(shù)
//2. 初始化，處理邊界問題
if(n == 1) {
return 1;
}
if(n == 2) {
return 2;
}
if(n == 3) {
return 4;
}
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
//3. 填表
for(int i = 4; i < n + 1; i++) {
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
}
//4. 返回值
return dp[n];
}
}
- 沒做一次加法就要取模一次！
- 因為取模滿足分配律，所以這樣子算得到的結(jié)果沒問題
3. 使用最小花費爬樓梯
傳送門：力扣746
題目：
3.1 題目解析
輸入一個cost數(shù)組，通過數(shù)組得到付費臺階數(shù)n，得到終點位置，輸出到達終點的最小花費
通過示例探索規(guī)律：
3.2 算法原理
3.2.1 狀態(tài)表示
很顯然，這要用到一維的順序結(jié)構(gòu)
且dp數(shù)組的大小為n + 1
題目要求：返回到達終點的最小花費（理解為到達第n個臺階）
經(jīng)驗：以某一個節(jié)點為終點或者以某一個節(jié)點為起點去研究
- 而答案應(yīng)該對應(yīng)到dp表中的dp[n]（其中一值）
- 這道題也因此分離出兩種解法（先將以某節(jié)點為終點的解法）
所以狀態(tài)表示就是：dp[i]代表從起點到 i 的最小消費
3.2.2 狀態(tài)轉(zhuǎn)移方程
同樣的，把dp[i]之前的值認為“已知”，以此為條件去推導(dǎo)dp[i]
我們要到達 i，那么我們到達前的位置可以是：i - 1，i - 2
- 到達i - 1，在原來支付的dp[i - 1]的基礎(chǔ)上支付cost[i - 1]，跳一步到dp[i]
- 到達i - 2，在原來支付的dp[i - 2]的基礎(chǔ)上支付cost[i - 2]，跳兩步到dp[i]
而我們需要取其較小值~
所以得到，dp[i] = min{dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]}
3.2.3 初始化
對于0和1下標要進行一些初始化~
到達0和1并不需要支付，所以值為0~
3.2.4 填表順序
由于是以i節(jié)點為終點，dp[i]之前的點為條件，所以順序為左到右
3.2.5 返回值
返回dp[n]，其代表第n個臺階（終點）的最小花費~
3.3 編寫代碼
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
//1. 創(chuàng)建dp表
int[] dp = new int[n + 1];
//2. 初始化，處理邊界
if(n == 0 || n == 1) {
return 0;
}
dp[0] = 0;
dp[1] = 0;
//3. 填表
for(int i = 2; i < n + 1; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
//4. 返回值
return dp[n];
}
}
- 直接根據(jù)剛才的算法分析寫就行了~
3.4 解法2：以某節(jié)點為起點
得到狀態(tài)表示為：dp[i] 代表 第i個臺階跳到終點的最小花費
- 所以返回值為dp[0] 或者dp[1]的最小值
- 填表順序為從右往左
3.4.1 得到狀態(tài)轉(zhuǎn)移方程
我們認定從dp[i]以后的值為“已知”，利用它們得到結(jié)果，從第i個臺階到終點的接下來的一步，要么到達i + 1,要么到達i + 2：
- 到達i + 1，支付cost[i]的基礎(chǔ)上支付dp[i + 1]后到達終點
- 到達i + 2，支付cost[i]的基礎(chǔ)上支付dp[i + 2]后到達終點
并且取其較小值最為dp[i]
所以方程為：dp[i] = min{dp[i + 1], dp[i + 2]} + cost[i];
3.4.2 初始化
dp[n]為終點，值為0
dp[n - 1]到終點只有一步之遙，值為cost[n - 1]
3.4.3 編寫代碼
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
//1. 創(chuàng)建dp表
int[] dp = new int[n + 1];
//2. 初始化，處理邊界
if(n == 0 || n == 1) {
return 0;
}
dp[n] = 0;
dp[n - 1] = cost[n - 1];
//3. 填表
for(int i = n - 2; i >= 0; i--) {
dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
}
//4. 返回值
return Math.min(dp[0], dp[1]);
}
}
所以狀態(tài)表示的不同，算法思路就有所不同，至于怎么選中呢？
- 做題多，經(jīng)驗多
- 想到一個，就想盡方法去用這一個去解決問題，解決不了再換（敢于嘗試）
4. 解碼方法
傳送門：力扣91
題目：
4.1 題目解析
對于示例，目前看不出什么~
4.2 算法原理
4.2.1 狀態(tài)表示
顯然，也是一維的dp表（大小為n）
題目要求：輸入字符串，返回整個字符串能反解出來的解的個數(shù)
經(jīng)驗：以某個節(jié)點為終點
- 那么這個終點只能是字符串的某個字符了~
- 而答案應(yīng)該為dp[n - 1]（dp表的其中一值）
那么我們趨向于讓答案合理的為dp[n - 1]:
得到狀態(tài)表示：dp[i]代表字符串[0, i]的子串最多能反解出來的解的個數(shù)
4.2.2 狀態(tài)轉(zhuǎn)移方程
同樣的，我們把dp[i]之前的值視為“已知”，把它們當做條件，去推導(dǎo)dp[i]
那么，要擴展到[0, i]的字符串，則擴展成[0, i]字符串之前，應(yīng)該為[0, i - 1]的子串或者[0, i - 2]的子串:
- 如果是[0, i - 1]的子串，則字符串的第i個字符應(yīng)該單獨轉(zhuǎn)化為字母才行，不然前功盡棄！
- 反解成功：dp[i - 1]
- 反解失?。?
- 如果是[0, i - 2]的子串，則字符串的第i - 1和第i個字符應(yīng)該成雙轉(zhuǎn)化為字母(06之類的不行！)才行，否則前功盡棄！
- 反解成功：dp[i - 2]
- 反解失?。?
- 為什么不可以各自可轉(zhuǎn)化為字母也行?
- 第i - 1個字符可以單獨反解和第i個字符也可以單獨反解，此解法在情況1出現(xiàn)過
得出狀態(tài)轉(zhuǎn)移方程：
dp[i] = (dp[i - 1]) + (dp[i - 2]);
- 前提是對應(yīng)項滿足條件
4.2.3 初始化
對于0和1下標要特殊處理：
-
0的話
- 如果可以單獨成字母 => 1
- 不可以 => 0
-
1的話
- 成雙結(jié)合成字母 => +1
- 各自單獨成字母 => +1
- 都不可以 => 0
4.2.4 填寫順序
由于是以某個節(jié)點為終點，所以填寫順序為從左到右~
4.2.5 返回值
返回dp[n - 1]，代表整個字符串能反解的解的個數(shù)
4.3 編寫代碼
class Solution {
public int numDecodings(String s) {
int n = s.length();
char[] string = s.toCharArray();
//創(chuàng)建dp表
int[] dp = new int[n];
//初始化并處理邊界問題
if(string[0] != '0') {
dp[0] = 1;
}
if(n == 1) {
return dp[0];
}
if(string[0] !='0' && string[1] != '0') {
dp[1]++;
}
int number = (string[0] - '0') * 10 + string[1] - '0';
if(number >= 10 && number <= 26) {
dp[1]++;
}
for(int i = 2; i < n; i++) {
if(string[i] != '0') {
dp[i] += dp[i - 1];
}
number = (string[i - 1] - '0') * 10 + string[i] - '0';
if(number >= 10 && number <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n - 1];
}
}
- 總體代碼跟剛才的原理對應(yīng)，理解起來也沒啥問題
- 但是明顯的，這個初始化未免也太長了吧~
而且，跟填表操作還差不多：
- 寫得很別扭~
4.4 代碼簡化技巧
- 這就衍生出一種做法，就是在添加一個“假的數(shù)據(jù)“，而這個假的數(shù)據(jù)仍讓狀態(tài)轉(zhuǎn)移方程成立~
- 這樣就可以將重復(fù)的代碼放在一起了~
而這個fake為多少呢，一般是為0的，但是一定要據(jù)實際而言！
- 這道題fake為1才對，因為string[1]和string[2]組成功后，是一種才對，所以dp[0]=1
所以新dp表的大小為n + 1，返回值為dp[n]；
注意這里的dp[i]代表的是[0, i)的字符串子串！
class Solution {
public int numDecodings(String s) {
int n = s.length();
char[] string = s.toCharArray();
int[] dp = new int[n + 1];
dp[0] = 1;
if(string[0] != '0') {
dp[1] += 1;
}
if(n == 1) {
return dp[1];
}
for(int i = 2; i < n + 1; i++) {
if(string[i - 1] != '0') {
dp[i] += dp[i - 1];
}
int number = (string[i - 2] - '0') * 10 + string[i - 1] - '0';
if(number >= 10 && number <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}
這個小優(yōu)化能掌握是更好的~
文章到此結(jié)束！謝謝觀看
可以叫我 小馬，我可能寫的不好或者有錯誤，但是一起加油鴨??！動態(tài)規(guī)劃第一章結(jié)束啦，本章節(jié)講解的類型都差不多，是不是有點“斐波那契”那味！已知推未知！牢記思想流程，特別重要
如果你理解的不錯，那你很有天賦！
這動態(tài)規(guī)劃的第一步走的不錯！文章來源：http://www.zghlxwxcb.cn/news/detail-483280.html
本文代碼鏈接：碼云文章來源地址http://www.zghlxwxcb.cn/news/detail-483280.html
到了這里，關(guān)于【動態(tài)規(guī)劃】斐波那契數(shù)列模型的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
