關(guān)于動(dòng)態(tài)規(guī)劃，你想知道的都在這里了！

來自公眾號(hào)：AI科技大本營(yíng)

作者：Your DevOps Guy
翻譯：火火醬~，責(zé)編：晉兆

什么是動(dòng)態(tài)規(guī)劃？它又有什么重要的呢？

動(dòng)態(tài)規(guī)劃

• 最優(yōu)子結(jié)構(gòu)（Optimal substructure）
• 重疊子問題（Overlapping subproblems）

F(0)?=?F(1)?=?1
F(n)?=?F(n-1)?+?F(n-2)

大家都說一張圖片勝過千言萬語，所以......（摘自《Elements of programming interviews》） ? ? ? ? ? ? ?

• 要想解決一個(gè)大小為n的問題，我們可以調(diào)用相同的函數(shù)來解決同一問題的一個(gè)實(shí)例，但實(shí)例規(guī)模比原始問題規(guī)模小一些。
• 我們一直不斷地調(diào)用該函數(shù)，直到到達(dá)基礎(chǔ)用例，也就是停止條件，在此處即n = 0或n = 1。

遞歸和動(dòng)態(tài)規(guī)劃

• 多維（以及一維）數(shù)組——最常用的方法；
• 哈希表；
• 二叉搜索樹；

如何解決動(dòng)態(tài)規(guī)劃問題

• ... ...的前n個(gè)元素；
• ... ...的所有方式；
• 有多少種... ...方式；
• 第n個(gè)... ... ；
• ... ...的最優(yōu)解決方案；
• ... ...的最短小/最大/最短路徑；

• 證明重疊子問題和次優(yōu)結(jié)構(gòu)特性。
• 定義子問題。
• 定義遞歸。
• 編寫自上而下或自下而上的動(dòng)態(tài)規(guī)劃解決方案。

	時(shí)間~子問題個(gè)數(shù)*每個(gè)子問題的時(shí)間

示例

一維問題

（1）斐波那契

int?fib(int?n)?{
??if?(n?==?0?||?n?==?1)
????return?1;
??else
????return?fib(n?-?1)?+?fib(n?-?2);
??}
}

• 檢查我們需要的值是否已經(jīng)在緩存中了。如果是，就返回它。
• 如果不是，就在返回之前先緩存的解決方案。

int?fib(int?n)?{
??vector<int>?cache(n?+?1,?-1);
??return?fib_helper(n,?cache);
}
int?fib_helper(int?n,?vector<int>?&cache)?{
???if(-1?!=?cache[n])
?????return?cache[n];
???if?(n?==?0?||?n?==?1)
?????cache[n]?=?1;
??else
????cache[n]?=?fib_helper(n?-?1,?cache)?+?fib_helper(n?-?2,?cache);
??return?cache[n];
}

int?fib(int?n)?{
????vector<int>?f(n?+?1,?0);??
????f[1]?=?1;
????for(int?i?=?2;?i?<=?n;?i++)
???????f[i]?=?f[i?-?1]?+?f[i?-?2];
????return?f[n];
}

int?fib(int?n)?{??
????if?(n?==?0?||?n?==?1)
??????return?1;
????//Variables?that?represent?f(n?-?1),?f(n?-?2)?and?f(n)
????int?n1=?1,?n2?=?1,?f?=?0;
????for?(int?i?=?2;?i?<=?n;?i++)?{
????????f=?n1?+?n2;
????????n2?=?n1;
????????n1?=?f;
????}
????return?f;
}

• 幾個(gè)變量，或許我們就可以擺脫一維數(shù)組，將其變成幾個(gè)變量。
• 二維矩陣中的幾行，或許我們可以將其減少成幾個(gè)一維數(shù)組。
• 等等... ...

（2）爬樓梯

• 輸入：2
• 輸出：2
• 說明：有兩種方法可以爬到頂端：1階+1階和2階

• 輸入：3
• 輸出：3
• 說明：有三種方法可以爬到頂端：1階+ 1階+ 1階，1階+ 2階，2階+ 1階

• 要得到f（N），就要先求出f（N-1）和 f（N-2）。
• 要得到f（N-1），就要先求出f（N-2）和 f（N-3）。
• 要得到f（N-2），就要先求出f（N-3）和 f（N-4）。

• 這個(gè)問題有重疊的子問題：你需要多次計(jì)算f（N-2）， f（N-3）， f（N-4），... ...
• 這個(gè)問題向我們展現(xiàn)了最優(yōu)子結(jié)構(gòu)：通過f（N-1）和f（N-2）的最優(yōu)解，可以得到f（N）的最優(yōu)解。

（3）最長(zhǎng)遞增子序列

• 迭代數(shù)組中的每一個(gè)元素，我們稱其為X。
• 如果新元素Y大于X，那么序列可以擴(kuò)展一個(gè)元素。
• 如果我們已經(jīng)存儲(chǔ)了所有子問題的解，那么獲取新長(zhǎng)度是非常簡(jiǎn)單的——只需在數(shù)組中進(jìn)行查找即可。我們可以根據(jù)子問題的最優(yōu)解得出新問題的解。
• 返回新的最長(zhǎng)遞增子序列的長(zhǎng)度。

• 最優(yōu)子結(jié)構(gòu)：我們已經(jīng)證明了大小為n的問題的最優(yōu)解可以由子問題的最優(yōu)解計(jì)算出來。
• 重疊子問題：要想計(jì)算s（n），則需要s（0）， s（1），... ...，s（n-1）。同樣，要計(jì)算s（n-1），則需要s（0）， s（1），... ...，s（n-2）。同樣的問題需要進(jìn)行多次計(jì)算。

int?lengthOfLIS(const?vector<int>&?nums)?{
if(nums.empty())
return?0;
vector<int>?dp(nums.size(),?1);
int?maxSol?=?1;
for(int?i?=?0;?i?for(int?j?=?0;?j?if(nums[i]?>?nums[j]){
dp[i]?=?max(dp[i],?dp[j]?+?1);
}
}
maxSol?=?max(maxSol,?dp[i]);
}
return?maxSol;???
}

（4）有多少BST

• 輸入：5
• 輸出：42
• 說明：給定n = 5, 總共有42個(gè)唯一的BST

• 3是根
• 3的左邊是數(shù)字1和2
• 3的右邊是數(shù)字4和5

• 選一個(gè)元素作為BST的根；
• 解決（1到根-1）和（根+1到n）兩個(gè)數(shù)字的相同問題；
• 將每個(gè)子問題的兩個(gè)結(jié)果相乘；
• 將其加到我們的運(yùn)行總計(jì)上；
• 繼續(xù)下一個(gè)根；

int?numTrees(int?n)?{
vector<int>?dp(n?+?1,?0);
dp[0]?=?1;
dp[1]?=?1;
for(int?i?=?2;?i?<=?n;?++i){
for(int?j?=?0;?j?dp[i]?+=?dp[j]?*?dp[i?-?1?-?j];
}
}
return?dp.back();
}

二維問題

• 自上而下的解決方案和之前沒有太大的區(qū)別：找到遞歸并使用緩存。
• 對(duì)于自下而上的解決方案，一個(gè)2D數(shù)組就足以存儲(chǔ)結(jié)果了。像我之前提到的，可能會(huì)減少一個(gè)或幾個(gè)一維數(shù)組，但是沒有必要太在意。之所以提到這一點(diǎn)只是以防你在解決問題時(shí)看到會(huì)有點(diǎn)摸不著頭腦。

（1）最小路徑和

• 輸入：[ [1,3,1], [1,5,1], [4,2,1] ]
• 輸出：7
• 說明：因?yàn)槁窂?→3→1→1→1總和最小

int?minPathSum(const?vector<vector<int>>&?grid)?{
const?int?nrow?=?grid.size();
if(nrow?==?0)
return?0;
const?int?ncol?=?grid[0].size();
vector<vector<int>>?minSum(nrow,?vector<int>(ncol,?0));
minSum[0][0]?=?grid[0][0];
for(int?col?=?1;?col?minSum[0][col]?=?minSum[0][col?-?1]?+?grid[0][col];
for(int?row?=?1;?row?minSum[row][0]?=?minSum[row?-?1][0]?+?grid[row][0];
for(int?col?=?1;?col?for(int?row?=?1;?row?minSum[row][col]?=?min(minSum[row?-?1][col],?minSum[row][col?-?1])?+?grid[row][col];
}
}
return?minSum[nrow?-?1][ncol?-?1];
}

（2）背包問題

• 我們可以把這樣物品放到背包里（如果合適的話)，背包的總價(jià)值增加，容量減少。
• 我們可以放棄這樣物品，背包里的價(jià)值和容量不變。

//?Recursive.?Try?to?turn?this?into?a?piece?of?top-down?DP?code.int?knapSack(int?W,?int?wt[],?int?val[],?int?n)?{
????if?(n?==?0?||?W?==?0)
????????return?0;
????if?(wt[n?-?1]?>?W)
????????return?knapSack(W,?wt,?val,?n?-?1);
????else
????????return?max(val[n?-?1]?+?knapSack(W?-?wt[n?-?1],??wt,?val,?n?-?1),?knapSack(W,?wt,?val,?n?-?1));
}

//?C?style,?in?case?you?are?not?familiar?with?C++?vectorsint?knapSack(int?W,?int?wt[],?int?val[],?int?n)?{
????int?i,?w;
????int?K[n?+?1][W?+?1];
????for?(i?=?0;?i?<=?n;?i++)?{
????????for?(w?=?0;?w?<=?W;?w++)?{
????????????if?(i?==?0?||?w?==?0)
????????????????K[i][w]?=?0;
????????????else?if?(wt[i?-?1]?<=?w)
????????????????K[i][w]?=?max(?val[i?-?1]?+?K[i?-?1][w?-?wt[i?-?1]],?K[i?-?1][w]);
????????????else
????????????????K[i][w]?=?K[i?-?1][w];
????????}
????}
????return?K[n][W];
}

（3）最長(zhǎng)公共子序列

• 輸入：text 1 = “abcde”, text 2 = “ace”
• 輸出：3
• 說明：最長(zhǎng)公共子序列是?“ace” ，且其長(zhǎng)度為3

• 如果相等，那么LCS的長(zhǎng)度至少為1。我們需要調(diào)用f(A[0:n-1]， B[0:n-1])來查找該索引前的LCS，并加1，因?yàn)锳[n]和B[n]是相同的。
• 如果不相等，我們就刪除兩個(gè)字符串的最后一個(gè)字符——一次刪一個(gè)，并查找生成LCS的路徑。換句話說，我們?nèi)(A[0: n-1]， B)和f(A, B[0:n-1])的最大值。
• 重疊子問題：我們來看看可能會(huì)出現(xiàn)的調(diào)用：(“abcde”, “ace”)產(chǎn)生x1 = (“abcd”, “ace”)和y1 = (“abcde”, “ac”)；x1將產(chǎn)生x12 = (“abc”, “ace”) 和y12= (“abcd”, “ac”)；y1將產(chǎn)生(“abcd”, “ac”)和(“abcde”, “a”)。如你所見，同樣的問題需要計(jì)算很多次。
• 最優(yōu)子結(jié)構(gòu)：與最長(zhǎng)遞增子序列非常類似。如果我們?cè)谄渲幸粋€(gè)字符串A’中添加一個(gè)額外的字符，就可以從所有的緩存結(jié)果中快速計(jì)算出解決方案，而這些結(jié)果是我們解A和B得到的。

int?longestCommonSubsequence(const?string?&text1,?const?string?&text2)?{
const?int?n?=?text1.length();
const?int?m?=?text2.length();
vector<vector<int>>?dp(n?+?1,?vector<int>(m?+?1,0));
for(int?i?=?1;?i?<=?n;?i++){
??for(int?j?=?1;?j?<=?m;?j++){
????if(text1[i-1]?==?text2[j-1])
??????dp[i][j]?=?dp[i-1][j-1]+1;
????else?
??????dp[i][j]?=?max(dp[i-1][j],?dp[i][j-1]);
????}
}
return?dp[n][m];
}

總結(jié)

原文鏈接：

https://hackernoon.com/all-you-need-to-know-about-dynamic-programming-0tj3e5l

本文由AI科技大本營(yíng)翻譯，轉(zhuǎn)載請(qǐng)注明出處

推薦閱讀：
完全整理 | 365篇高質(zhì)技術(shù)文章目錄整理
算法之美 : 棧和隊(duì)列
主宰這個(gè)世界的10大算法
徹底理解cookie、session、token
淺談什么是遞歸算法
專注服務(wù)器后臺(tái)技術(shù)棧知識(shí)總結(jié)分享
歡迎關(guān)注交流共同進(jìn)步