關(guān)于動態(tài)規(guī)劃，你想知道的都在這里了！
來自公眾號：AI科技大本營
作者：Your DevOps Guy
翻譯：火火醬~，責(zé)編：晉兆
什么是動態(tài)規(guī)劃？它又有什么重要的呢？
動態(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)
? ? ?要想解決一個大小為n的問題，我們可以調(diào)用相同的函數(shù)來解決同一問題的一個實例，但實例規(guī)模比原始問題規(guī)模小一些。 我們一直不斷地調(diào)用該函數(shù)，直到到達(dá)基礎(chǔ)用例，也就是停止條件，在此處即n = 0或n = 1。
遞歸和動態(tài)規(guī)劃
多維（以及一維）數(shù)組——最常用的方法； 哈希表； 二叉搜索樹；
如何解決動態(tài)規(guī)劃問題
... ...的前n個元素； ... ...的所有方式； 有多少種... ...方式； 第n個... ... ； ... ...的最優(yōu)解決方案； ... ...的最短小/最大/最短路徑；
證明重疊子問題和次優(yōu)結(jié)構(gòu)特性。 定義子問題。 定義遞歸。 編寫自上而下或自下而上的動態(tài)規(guī)劃解決方案。
時間~子問題個數(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;
}
幾個變量，或許我們就可以擺脫一維數(shù)組，將其變成幾個變量。 二維矩陣中的幾行，或許我們可以將其減少成幾個一維數(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）。
這個問題有重疊的子問題：你需要多次計算f（N-2）， f（N-3）， f（N-4），... ... 這個問題向我們展現(xiàn)了最優(yōu)子結(jié)構(gòu)：通過f（N-1）和f（N-2）的最優(yōu)解，可以得到f（N）的最優(yōu)解。
（3）最長遞增子序列
迭代數(shù)組中的每一個元素，我們稱其為X。 如果新元素Y大于X，那么序列可以擴(kuò)展一個元素。 如果我們已經(jīng)存儲了所有子問題的解，那么獲取新長度是非常簡單的——只需在數(shù)組中進(jìn)行查找即可。我們可以根據(jù)子問題的最優(yōu)解得出新問題的解。 返回新的最長遞增子序列的長度。
最優(yōu)子結(jié)構(gòu)：我們已經(jīng)證明了大小為n的問題的最優(yōu)解可以由子問題的最優(yōu)解計算出來。 重疊子問題：要想計算s（n），則需要s（0）， s（1），... ...，s（n-1）。同樣，要計算s（n-1），則需要s（0）， s（1），... ...，s（n-2）。同樣的問題需要進(jìn)行多次計算。
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個唯一的BST
3是根 3的左邊是數(shù)字1和2 3的右邊是數(shù)字4和5
選一個元素作為BST的根； 解決（1到根-1）和（根+1到n）兩個數(shù)字的相同問題； 將每個子問題的兩個結(jié)果相乘； 將其加到我們的運(yùn)行總計上； 繼續(xù)下一個根；
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ū)別：找到遞歸并使用緩存。 對于自下而上的解決方案，一個2D數(shù)組就足以存儲結(jié)果了。像我之前提到的，可能會減少一個或幾個一維數(shù)組，但是沒有必要太在意。之所以提到這一點只是以防你在解決問題時看到會有點摸不著頭腦。
（1）最小路徑和
輸入：[ [1,3,1], [1,5,1], [4,2,1] ] 輸出：7 說明：因為路徑1→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）背包問題
我們可以把這樣物品放到背包里（如果合適的話)，背包的總價值增加，容量減少。 我們可以放棄這樣物品，背包里的價值和容量不變。
//?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）最長公共子序列
輸入：text 1 = “abcde”, text 2 = “ace” 輸出：3 說明：最長公共子序列是?“ace” ，且其長度為3
如果相等，那么LCS的長度至少為1。我們需要調(diào)用f(A[0:n-1]， B[0:n-1])來查找該索引前的LCS，并加1，因為A[n]和B[n]是相同的。 如果不相等，我們就刪除兩個字符串的最后一個字符——一次刪一個，并查找生成LCS的路徑。換句話說，我們?nèi)(A[0: n-1]， B)和f(A, B[0:n-1])的最大值。 重疊子問題：我們來看看可能會出現(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”)。如你所見，同樣的問題需要計算很多次。 最優(yōu)子結(jié)構(gòu)：與最長遞增子序列非常類似。如果我們在其中一個字符串A’中添加一個額外的字符，就可以從所有的緩存結(jié)果中快速計算出解決方案，而這些結(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科技大本營翻譯，轉(zhuǎn)載請注明出處
推薦閱讀：
完全整理 | 365篇高質(zhì)技術(shù)文章目錄整理
專注服務(wù)器后臺技術(shù)棧知識總結(jié)分享
歡迎關(guān)注交流共同進(jìn)步
評論
圖片
表情