作者 | Your DevOps Guy
翻譯| 火火醬~，責編 | 晉兆雨
在本文中，我將介紹由Richard Bellman在20世紀50年代提出的動態規劃（dynamic programming）概念，這是一種強大的算法設計技術——將問題分解成多個小問題，存儲它們的解，通過將其結合在一起，最終得到原始問題的解決方案。FAANG編程面試中最難的問題通常都屬於這一類。你在面試的過程中也很可能會被要求解決這樣的問題，因此，了解這項技術的重要性自然不言而喻。接下來，我將解釋什麼是動態規劃，給出一個解決動態規劃問題的秘訣，並且和大家一起分析幾個示例，以便你能夠更好地理解其應用場合和應用方法。和我以往有關編程面試的文章一樣，在本文中，我將分享自己在使用這種方法解決問題時的思考過程，這樣當你在面對其中一個問題時，按照這個過程一定也能解決。不需要死記硬背，我們只需要通過了解技術和實踐，將想法轉化成代碼技能。編程的重點不在於學習程式語言，而在於分析問題，考慮不同的解決方案，從中選出最優解，然後通過某種程式語言將其轉化為現實。動態規劃是一種解決最優化、搜索和計數問題的通用技術，這些問題都可以被分解為多個子問題。要應用動態規劃，問題就必須具備以下兩個屬性：
最優子結構（Optimal substructure）重疊子問題（Overlapping subproblems）如果大小為n的問題的最優解可以由大小小於n的問題的同一實例的最優解推導出，則該問題具有最優子結構。例如，如果從巴黎到莫斯科的最短路徑會經過柏林，那麼可以由巴黎到柏林的最短路徑和柏林到莫斯科的最短路徑組成。如果一個問題可以通過組合非重疊子問題的最優解來解決，這種策略被稱為分治法。這就是歸併排序和快速排序不屬於動態規劃問題的原因。舉一個大家都很熟悉的例子，斐波那契數列，即從第三項開始，每一項都等於前兩項之和。斐波那契數列可以表示為
F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2)
大家都說一張圖片勝過千言萬語，所以.（摘自《Elements of programming interviews》） 要想解出F（n），就需要解出F（n-1）和F（n-2），但是F（n-1）又需要F（n-2）和F（n-3）。這樣一來，F（n-2）是重複的，來自於同一個問題的兩個不同實例——計算一個斐波那契數。要想解決一個大小為n的問題，我們可以調用相同的函數來解決同一問題的一個實例，但實例規模比原始問題規模小一些。我們一直不斷地調用該函數，直到到達基礎用例，也就是停止條件，在此處即n = 0或n = 1。從概念上講，動態規劃涉及到遞歸問題。我們希望通過同一個問題的較小實例來解決原始問題，而遞歸是在代碼中實現這一點的最佳選擇。與純遞歸函數的不同之處在於，我們將用空間來換取時間：我們將存儲各子問題的最優解，進而高效地找到原始問題的最優解。當然，這並不是說我們都必須使用遞歸來解決動態規劃問題。還可以通過一種迭代方法來編寫動態規劃解決方案。我們需要將所有子問題的解決方案填入表格（從基本用例開始），並用它來構建我們正在尋找的解決方案。這個過程是通過迭代的方式完成的，你可以從下面列別中任選其一作為存儲子問題解決方案的數據結構：或許現在看起來有點糊塗，但等一會兒講到示例後，一切都會清楚得多。如果一個問題想要通過動態規劃來解決的話，就必須具備最優子結構和重疊子問題這兩個屬性。當直覺告訴你動態規劃或許是一個可行的解決方案時，你需要驗證其是否具備這兩個屬性。下面讓我們試著感受一下，什麼樣的問題可以用動態規劃來解決。一切以「找到」開頭的問題：很不幸，解決動態規劃問題並沒有什麼通用秘訣。我們需要在經歷過很多問題之後，才能逐漸掌握其訣竅。這確實不容易，畢竟這可能會是你在面試中遇到的最難的問題了。但也先不要氣餒，簡單來講，就是用相對簡單的工具針對問題進行建模，並不需要花哨的數據結構或算法。我已經解決過很多此類問題了，但有時還是會覺得毫無頭緒，找不到解決方法。練習得越多，就越容易。以下這幾點或許能帶你走近解決動態規劃問題的秘訣：複雜度分析因問題而異，但一般來說，時間複雜度可以表示為：
計算自下而上解決方案的空間複雜度很簡單，因為其等於存儲子問題解決方案所需的空間（多維數組）。我已經根據所涉及的獨立維度的數量對問題進行了分類。這一步並不是必須的，但我發現在設計解決方案時，遵循一定的心理模型是非常有用的。隨著編寫的代碼越來越多，你會找到一些模式，而這就是其中之一。不妨試一下，如果覺得有用的話就用起來吧。因為現在大家都已經對這個問題非常熟悉了，所以我就直接給出遞歸解決方案：
int fib(int n) {
if (n == 0 || n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
}
檢查我們需要的值是否已經在緩存中了。如果是，就返回它。
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];
}
這種方法可以進一步優化內存，但並不會優化時間（也可以通過其他技術更快地計算斐波納契數列，但這就是另一篇文章的內容了），只需要使用3個變量，而不必使用數組，因為我們只需要跟蹤兩個值，即f （n - 1）和f （n - 2），就可以得到我們想要的輸出——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;
}
幾個變量，或許我們就可以擺脫一維數組，將其變成幾個變量。二維矩陣中的幾行，或許我們可以將其減少成幾個一維數組。通過降維，我們提高了空間的複雜度。現在，你不必記住所有的細節，但在進行過一些實踐之後，要試著自己提出這些優化方案，從而增強自己分析問題並將想法轉化為代碼的能力。在面試中，我會選擇更簡單的版本，只討論潛在的優化方案。只有在編寫了自己的「標準化」動態規劃解決方案，並且時間充足的時候，才動手實施這些優化。假設你正在爬一段有n個臺階的樓梯，每次可以爬1或2個臺階。那麼要想爬到頂端的話，一共有多少種不同的方法呢？說明：有三種方法可以爬到頂端：1階+ 1階+ 1階，1階+ 2階，2階+ 1階先試著自己解決一下這個問題。你可能會想到一個遞歸解決方案。回顧一下我的說明和前面的示例，看看是否可以自行編寫出自上而下的的解決方案。提示一下：既然這個問題以「有多少種方式」開頭，那就應該能想到採用動態規劃的潛在可能性。在這種情況下，如果想要到達第N階，就要經過第N-1階或第N-2階，因為一次可以爬1階或2階。如果我們能解決這兩個子問題的話，就可以找到一般問題的解。我們將f（N）稱為到第N階的方法數。要得到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），... ...這個問題向我們展現了最優子結構：通過f（N-1）和f（N-2）的最優解，可以得到f（N）的最優解。因為我已經在上一個例子中寫過代碼了，所以這裡就不再寫代碼了。大家可以在下方連結中試著編寫並測試一下自己的解決方案。（連結地址：https://leetcode.com/problems/climbing-stairs/?ref=hackernoon.com）給定一個未排序的整數數組，求最長遞增子序列的長度。例如，對於數組[10,9,2,5,3,7,101,18]而言，其輸出為4，即序列[2,3,7,101]我們需要找到大小為n的數組的最長遞增子序列的長度。這聽起來像是一個可以通過動態規劃來解決的優化問題，那麼讓我們來試一下。假設我們已經有了大小為N的問題的解，稱其為s（n）,然後我們在數組中增加了一個額外元素，稱為Y。那麼，你能重複使用X的解決方案來解決這個新問題麼？這個問題通常會為我們帶來一些啟發。在這裡，我們需要知道新元素是否可以擴展任一現有序列：如果我們已經存儲了所有子問題的解，那麼獲取新長度是非常簡單的——只需在數組中進行查找即可。我們可以根據子問題的最優解得出新問題的解。最優子結構：我們已經證明了大小為n的問題的最優解可以由子問題的最優解計算出來。重疊子問題：要想計算s（n），則需要s（0）， s（1），... ...，s（n-1）。同樣，要計算s（n-1），則需要s（0）， s（1），... ...，s（n-2）。同樣的問題需要進行多次計算。
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 < nums.size(); ++i){
for(int j = 0; j < i; ++j){
if(nums[i] > nums[j]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxSol = max(maxSol, dp[i]);
}
return maxSol;
}
大家可以在下方連結中試著編寫並測試一下自己的解決方案。
（連結地址：https://leetcode.com/problems/longest-increasing-subsequence/?ref=hackernoon.com）對於給定的n，有多少結構唯一的存儲值為1... ...n的BST（二叉搜索樹）？我們一起來看看這個例子。假設我們有數字1、2、3、4、5，如何定義BST？我只需要選擇其中一個數作為根，先假設其為數字3，則：我們可以解決（1，2）和（4，5）的相同子問題（暫且稱其為解決方案L和R），數一數以3為根可以形成多少個BST，即L*R。如果我們對每一個可能的根都這樣做，並且把所有的結果相加的話，就可以得到我們所需的解決方案C（n）。如你所見，有條不紊地從幾個例子出發，可以幫助我們更好地設計算法。解決（1到根-1）和（根+1到n）兩個數字的相同問題；實際上，我們並不關心數組兩邊的數字是什麼。我們只需要子樹的大小，即根的左右兩邊的元素個數。這個問題中的每個實例都會產生相同的結果。在之前的例子中，L和R都是C（2）的解。我們只需要計算一次C（2），緩存，然後重複使用即可。
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 < i; ++j){
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp.back();
}
大家可以在下方連結中試著編寫並測試一下自己的解決方案。
（連結地址：https://leetcode.com/problems/unique-binary-search-trees/?ref=hackernoon.com）這些問題通常比較難建模，因為它涉及兩個維度。常見的例子是，在兩個字符串中迭代，或移動映射。自上而下的解決方案和之前沒有太大的區別：找到遞歸併使用緩存。對於自下而上的解決方案，一個2D數組就足以存儲結果了。像我之前提到的，可能會減少一個或幾個一維數組，但是沒有必要太在意。之所以提到這一點只是以防你在解決問題時看到會有點摸不著頭腦。我曾在另一篇文章中說過，學習是迭代的。首先，要把注意力集中在理解基礎知識上，然後再一點一點地增加更多的細節。給定m×n的非負數網格，找出一條從左上到右下的路徑，使路徑上所有數字之和最小。輸入：[ [1,3,1], [1,5,1], [4,2,1] ]最小化問題應該會讓你想到動態規劃。進一步分析，路徑可以經過任意單元格C（i，j）（即不在上邊框或左邊框），單元格A = （i-1, j）和B=（i，j-1）。由此，我們發現，有些問題需要進行多次計算。此外，我們如果知道A和B的最優解，就可以計算出當前單元格的最優解為min(sol (A)，sol(B)) + 1，因為我們只能通過當前單元格來表示A或B，要想移動到當前單元格就需要多走一步。換句話說，這是一個最優子結構和重疊問題。我們可以使用動態規劃。
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 < ncol; ++col)
minSum[0][col] = minSum[0][col - 1] + grid[0][col];
for(int row = 1; row < nrow; ++row)
minSum[row][0] = minSum[row - 1][0] + grid[row][0];
for(int col = 1; col < ncol; ++col){
for(int row = 1; row < nrow; ++row){
minSum[row][col] = min(minSum[row - 1][col], minSum[row][col - 1]) + grid[row][col];
}
}
return minSum[nrow - 1][ncol - 1];
}
邊界條件定義在矩陣的邊界上。只有一種方法可以獲得邊界上的點：從上一個點向右或向下移動一個格子。大家可以在下方連結中試著編寫並測試一下自己的解決方案。（連結地址：https://leetcode.com/problems/minimum-path-sum/?ref=hackernoon.com）給定兩個整數數組val[0..n - 1]和wt [0 . .n-1]，分別表示與n個物品相關的值和權重。同時，給定一個代表背包容量的整數W，求val [ ]的最大值子集，保證這個子集的權重之和小於或等於W。背包裡的物品都必須保持完整，要麼選擇完整的物品，要麼不選（0 - 1屬性）。試著想出一個遞歸解決方案。在此基礎上，添加一個緩存層，我們就會得到一個自上而下的動態規劃解決方案了！我們可以把這樣物品放到背包裡（如果合適的話)，背包的總價值增加，容量減少。在試過所有組合之後，我們只選擇最大值。這個過程極其緩慢，但卻是邁向最終解決方案的第一步。我們必須在兩個選項之間做出決定（向集合中添加一個元素或跳過它），在許多問題中都面臨這樣的選擇，所以我們一定要了解，並理解其應用場合和方式。
// 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];
}
給定兩個字符串text 1和text 2，返回它們最長公共子序列的長度。字符串的子序列是在不改變其餘字符相對順序的情況下，從原字符串中刪除一些字符（也可以不刪除）後生成的新字符串，例如，「ace」是「abcde」的子序列，但「aec」不是。兩個字符串共同的子序列就被稱為其公共子序列。輸入：text 1 = 「abcde」, text 2 = 「ace」說明：最長公共子序列是 「ace」 ，且其長度為3同樣，計算最長X的問題，動態規劃應該可以幫得上忙。鑑於大家已經有了一些動態規劃的經驗了，我就直接從示例中的兩個屬性說起。我們將字符串稱為A和B，這個問題的解為f（A, B），解題思路是看最後兩個字符是否相等：如果相等，那麼LCS的長度至少為1。我們需要調用f(A[0:n-1]， B[0:n-1])來查找該索引前的LCS，並加1，因為A[n]和B[n]是相同的。如果不相等，我們就刪除兩個字符串的最後一個字符——一次刪一個，並查找生成LCS的路徑。換句話說，我們取f(A[0: n-1]， B)和f(A, B[0:n-1])的最大值。重疊子問題：我們來看看可能會出現的調用：(「abcde」, 「ace」)產生x1 = (「abcd」, 「ace」)和y1 = (「abcde」, 「ac」)；x1將產生x12 = (「abc」, 「ace」) 和y12= (「abcd」, 「ac」)；y1將產生(「abcd」, 「ac」)和(「abcde」, 「a」)。如你所見，同樣的問題需要計算很多次。最優子結構：與最長遞增子序列非常類似。如果我們在其中一個字符串A』中添加一個額外的字符，就可以從所有的緩存結果中快速計算出解決方案，而這些結果是我們解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];
}
大家可以在下方連結中試著編寫並測試一下自己的解決方案。（連結地址：https://leetcode.com/problems/longest-common-subsequence/?ref=hackernoon.com）我們一定要了解這些問題，因為很多其他問題都只是在此基礎上的變種而已，但是不要死記硬背。主動去了解動態規劃的使用場景和應用方式，並堅持練習，直到可以輕鬆地將自己的想法轉換成代碼。如你所見，這是需要講究方法的。我們不一定要用到高級的算法或數據結構知識才能解決問題，數組就足夠了。
我沒有完成時間/空間複雜度分析，大家可以把它作為課後練習。歡迎大家隨時在評論中留言，提出問題或分享觀點。
原文連結：
https://hackernoon.com/all-you-need-to-know-about-dynamic-programming-0tj3e5l
本文由AI科技大本營翻譯，轉載請註明出處