深入淺出動態規劃演算法(中)
開啟掘金成長之旅！這是我參與「掘金日新計劃 · 12 月更文挑戰」的第24天，點選檢視活動詳情。
學習目標：徹底搞懂最優子結構、無後效性和重複子問題。什麼樣的問題可以用動態規劃解決？解決動態規劃問題的一般思考過程是什麼樣的？貪心、分治、回溯、動態規劃這四種演算法思想又有什麼區別和聯絡？
一，“一個模型三個特徵”理論講解
一個模型指的是適合用動態規劃演算法解決的問題的模型，這個模型也被定義為“多階段決策最優解模型”。具體解釋如下：
一般是用動態規劃來解決最優問題。而解決問題的過程，需要經歷多個決策階段。每個決策階段都對應著一組狀態。然後我們尋找一組決策序列，經過這組決策序列，能夠產生最終期望求解的最優值。
1. 最優子結構
最優子結構指的是，問題的最優解包含子問題的最優解。反過來說就是，我們可以通過子問題的最優解，推匯出問題的最優解。把最優子結構，對應到前面定義的動態規劃問題模型上，就是後面階段的狀態可以通過前面階段的狀態推匯出來。
2. 無後效性
無後效性有兩層含義，第一層含義是，在推導後面階段的狀態的時候，我們只關心前面階段的狀態值，不關心這個狀態是怎麼一步一步推匯出來的。第二層含義是，某階段狀態一旦確定，就不受之後階段的決策影響。無後效性是一個非常“寬鬆”的要求。只要滿足前面提到的動態規劃問題模型，其實基本上都會滿足無後效性。
3. 重複子問題
不同的決策序列，到達某個相同的階段時，可能會產生重複的狀態。
4. “一個模型三個特徵”例項剖析
結合一個具體的動態規劃問題更能詳細理解上述理論，示例問題描述如下：
假設我們有一個 n 乘以 n 的矩陣 w[n][n]。矩陣儲存的都是正整數。棋子起始位置在左上角，終止位置在右下角。我們將棋子從左上角移動到右下角。每次只能向右或者向下移動一位。從左上角到右下角，會有很多不同的路徑可以走。我們把每條路徑經過的數字加起來看作路徑的長度。那從左上角移動到右下角的最短路徑長度是多少呢？
min_dist(i, j) 可以通過 min_dist(i, j-1) 和 min_dist(i-1, j) 兩個狀態推匯出來，所以這個問題符合“最優子結構”。
cpp
min_dist(i, j) = min(min_dist(i-1,j), min_dist(i, j-1))
二，兩種動態規劃解題思路總結
知道了如何鑑別一個問題是否可以用動態規劃來解決，接下來就是總結動態規劃解決問題的一般思路。解決動態規劃問題，一般有兩種思路。分別叫作：狀態轉移表法和狀態轉移方程法。
1. 狀態轉移表法
一般能用動態規劃解決的問題，都可以使用回溯演算法的暴力搜尋解決。所以，當我們拿到問題的時候，我們可以先用簡單的回溯演算法解決，然後定義狀態，每個狀態表示一個節點，然後對應畫出遞迴樹。從遞迴樹中，我們很容易可以看出來，是否存在重複子問題，以及重複子問題是如何產生的。以此來尋找規律，看是否能用動態規劃解決。
找到重複子問題之後，接下來，我們有兩種處理思路，第一種是直接用回溯加“備忘錄”的方法，來避免重複子問題。從執行效率上來講，這跟動態規劃的解決思路沒有差別。第二種是使用動態規劃的解決方法，狀態轉移表法。
我們先畫出一個狀態表。狀態表一般都是二維的，所以你可以把它想象成二維陣列。其中，每個狀態包含三個變數，行、列、陣列值。我們根據決策的先後過程，從前往後，根據遞推關係，分階段填充狀態表中的每個狀態。最後，我們將這個遞推填表的過程，翻譯成程式碼，就是動態規劃程式碼了。
適合狀態是二維的情況，再多維的話就不適合了，畢竟人腦不適合處理高維度的問題。
起點到終點，有很多種不同的走法，回溯演算法比較適合無重複又不遺漏地窮舉出所有走法，從而對比找出一個最短走法。
1，回溯解法的 C++ 程式碼如下：
cpp
// leetcode64. 最小路徑和. 回溯法-會超出時間限制
class Solution {
private:
int minDist = 10000;
void minDistBT(vector<vector<int>>& grid, int i, int j, int dist, int m, int n) {
if (i == 0 && j == 0) dist = grid[0][0];
if (i == m-1 && j == n-1) {
if (dist < minDist) minDist = dist;
return;
}
if (i < m-1) {
minDistBT(grid, i + 1, j, dist + grid[i+1][j], m, n); // 向右走
}
if (j < n-1) {
minDistBT(grid, i, j + 1, dist + grid[i][j+1], m, n); // 向下走
}
}
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int dist = 0;
minDistBT(grid, 0, 0, dist, m, n);
return minDist;
}
};
有了回溯程式碼之後，接下來，自然要畫出遞迴樹，以此來尋找重複子問題。在遞迴樹中，一個狀態（也就是一個節點）包含三個變數 (i, j, dist)，其中 i，j 分別表示行和列，dist 表示從起點到達 (i, j) 的路徑長度。從圖中，可以看出，儘管 (i, j, dist) 不存在重複，但是 (i, j) 重複的有很多。對於 (i, j) 重複的節點，我們只需要選擇 dist 最小的節點，繼續遞迴求解，其他節點就可以捨棄了。
2，動態規劃解法的 C++ 程式碼如下：
```cpp
// 對應 leetcode64. 最小路徑和
class Solution { // 動態規劃：狀態轉移表法
public:
int minPathSum(vector
// 分階段求解，下層狀態的值是基於上一層狀態來的
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
states[i][j] = grid[i][j] + std::min(states[i-1][j],states[i][j-1]);
}
}
return states[m-1][n-1];
}
}; ```
2. 狀態轉移方程法
根據最優子結構，寫出遞迴公式，也就是所謂的狀態轉移方程。狀態轉移方程，或者說遞迴公式是解決動態規劃的關鍵。遞迴加“備忘錄”的方式，將狀態轉移方程翻譯成來 C++ 程式碼。
cpp
// 狀態轉移方程
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
```cpp
// 對應 leetcode64. 最小路徑和
class Solution { // 狀態轉移方程法
private:
int minDist(int i, int j, vector
int minUp = 10000;
if (i - 1 >= 0) minUp = minDist(i - 1, j, matrix, mem);
int minLeft = 10000;
if (j - 1 >= 0) minLeft = minDist(i, j - 1, matrix, mem);
int currMinDist = matrix[i][j] + std::min(minUp, minLeft);
mem[i][j] = currMinDist;
return currMinDist;
}
public:
int minPathSum(vector
return minDist(m - 1, n - 1, grid, mem);
}
}; ```
三，四種演算法比較分析
如果將這四種演算法思想分一下類，那貪心、回溯、動態規劃可以歸為一類，而分治單獨可以作為一類，因為它跟其他三個都不大一樣。為什麼這麼說呢？因為前三個演算法解決問題的模型，都可以抽象成多階段決策最優解模型，而分治演算法解決的問題儘管大部分也是最優解問題，但是，大部分都不能抽象成多階段決策模型。
儘管動態規劃比回溯演算法高效，但是，並不是所有問題，都可以用動態規劃來解決。能用動態規劃解決的問題，需要滿足三個特徵，最優子結構、無後效性和重複子問題。在重複子問題這一點上，動態規劃和分治演算法的區分非常明顯。分治演算法要求分割成的子問題，不能有重複子問題，而動態規劃正好相反，動態規劃之所以高效，就是因為回溯演算法實現中存在大量的重複子問題。
貪心演算法實際上是動態規劃演算法的一種特殊情況。它解決問題起來更加高效，程式碼實現也更加簡潔。不過，它可以解決的問題也更加有限。它能解決的問題需要滿足三個條件，最優子結構、無後效性和貪心選擇性（這裡我們不怎麼強調重複子問題）。其中，最優子結構、無後效性跟動態規劃中的無異。“貪心選擇性”的意思是，通過區域性最優的選擇，能產生全域性的最優選擇。每一個階段，我們都選擇當前看起來最優的決策，所有階段的決策完成之後，最終由這些區域性最優解構成全域性最優解。
四，內容總結
什麼樣的問題適合用動態規劃解決？這些問題可以總結概括為“一個模型三個特徵”。其中，“一個模型”指的是，問題可以抽象成分階段決策最優解模型。“三個特徵”指的是最優子結構、無後效性和重複子問題。
哪兩種動態規劃的解題思路？它們分別是狀態轉移表法和狀態轉移方程法。其中，狀態轉移表法解題思路大致可以概括為，回溯演算法實現 - 定義狀態 - 畫遞迴樹 - 找重複子問題 - 畫狀態轉移表 - 根據遞推關係填表 - 將填表過程翻譯成程式碼。狀態轉移方程法的大致思路可以概括為，找最優子結構 - 寫狀態轉移方程 - 將狀態轉移方程翻譯成程式碼。
練習題
假設我們有幾種不同幣值的硬幣 v1，v2，……，vn（單位是元）。如果我們要支付 w 元，求最少需要多少個硬幣。比如，我們有 3 種不同的硬幣，1 元、3 元、5 元，我們要支付 9 元，最少需要 3 個硬幣（3 個 3 元的硬幣）。
參考資料
- 深入淺出動態規劃演算法(中)
- 深度學習煉丹-資料預處理和增強
- 深入淺出回溯演算法
- 深入淺出動態規劃演算法(上)
- GitHub 車牌檢測識別專案調研
- 卷積神經網路壓縮方法總結
- 神經網路模型複雜度分析
- MobileNetv1 論文詳解
- ShuffleNetv2論文詳解
- Pytorch基礎-tensor資料結構
- Fast YOLO：用於實時嵌入式目標檢測（附論文下載）
- 嵌入式新聞早班車-第24期
- SSD7 | 對嵌入式友好的目標檢測網路，產品落地
- SSD7-FFAM | 對嵌入式友好的目標檢測網路，為幼兒園兒童的安全保駕護航
- 如何用FPGA在嵌入式視覺應用實現機器學習
- 嵌入式、快速人臉演算法庫Vision.Face SDK開放下載！已經商用檢驗