掌握動態規劃，從“什么問題適合用”及“解題思路”入手

摘要：一般是用動態規劃來解決最優問題，

本文分享自華為云社區《深入淺出動態規劃演算法(中)》，作者：嵌入式視覺 ，

一，“一個模型三個特征”理論講解

一個模型指的是適合用動態規劃演算法解決的問題的模型，這個模型也被定義為“多階段決策最優解模型”，具體解釋如下：

一般是用動態規劃來解決最優問題，而解決問題的程序，需要經歷多個決策階段，每個決策階段都對應著一組狀態，然后我們尋找一組決策序列，經過這組決策序列，能夠產生最終期望求解的最優值，

1.最優子結構

最優子結構指的是，問題的最優解包含子問題的最優解，反過來說就是，我們可以通過子問題的最優解，推匯出問題的最優解，把最優子結構，對應到前面定義的動態規劃問題模型上，就是后面階段的狀態可以通過前面階段的狀態推匯出來，

2.無后效性

無后效性有兩層含義，第一層含義是，在推導后面階段的狀態的時候，我們只關心前面階段的狀態值，不關心這個狀態是怎么一步一步推匯出來的，第二層含義是，某階段狀態一旦確定，就不受之后階段的決策影響，無后效性是一個非常“寬松”的要求，只要滿足前面提到的動態規劃問題模型，其實基本上都會滿足無后效性，

3.重復子問題

不同的決策序列，到達某個相同的階段時，可能會產生重復的狀態，

4.“一個模型三個特征”實體剖析

結合一個具體的動態規劃問題更能詳細理解上述理論，示例問題描述如下：

假設我們有一個 n 乘以 n 的矩陣 w[n][n]，矩陣存盤的都是正整數，棋子起始位置在左上角，終止位置在右下角，我們將棋子從左上角移動到右下角，每次只能向右或者向下移動一位，從左上角到右下角，會有很多不同的路徑可以走，我們把每條路徑經過的數字加起來看作路徑的長度，那從左上角移動到右下角的最短路徑長度是多少呢？

min_dist(i, j) 可以通過 min_dist(i, j-1) 和 min_dist(i-1, j) 兩個狀態推匯出來，所以這個問題符合“最優子結構”，

min_dist(i, j) = min(min_dist(i-1,j), min_dist(i, j-1))

二，兩種動態規劃解題思路總結

知道了如何鑒別一個問題是否可以用動態規劃來解決，接下來就是總結動態規劃解決問題的一般思路，解決動態規劃問題，一般有兩種思路，分別叫作：狀態轉移表法和狀態轉移方程法，

1.狀態轉移表法

一般能用動態規劃解決的問題，都可以使用回溯演算法的暴力搜索解決，所以，當我們拿到問題的時候，我們可以先用簡單的回溯演算法解決，然后定義狀態，每個狀態表示一個節點，然后對應畫出遞回樹，從遞回樹中，我們很容易可以看出來，是否存在重復子問題，以及重復子問題是如何產生的，以此來尋找規律，看是否能用動態規劃解決，

找到重復子問題之后，接下來，我們有兩種處理思路，第一種是直接用回溯加“備忘錄”的方法，來避免重復子問題，從執行效率上來講，這跟動態規劃的解決思路沒有差別，第二種是使用動態規劃的解決方法，狀態轉移表法，

我們先畫出一個狀態表，狀態表一般都是二維的，所以你可以把它想象成二維陣列，其中，每個狀態包含三個變數，行、列、陣列值，我們根據決策的先后程序，從前往后，根據遞推關系，分階段填充狀態表中的每個狀態，最后，我們將這個遞推填表的程序，翻譯成代碼，就是動態規劃代碼了，

適合狀態是二維的情況，再多維的話就不適合了，畢竟人腦不適合處理高維度的問題，

起點到終點，有很多種不同的走法，回溯演算法比較適合無重復又不遺漏地窮舉出所有走法，從而對比找出一個最短走法，

（1）回溯解法的 C++ 代碼如下：

// 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++ 代碼如下：

// 對應 leetcode64. 最小路徑和
class Solution { // 動態規劃：狀態轉移表法
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > states(m, vector<int>(n, 0));
 // 第一個階段初始化
        int sum = 0;
 for(int i=0; i<n;i++){ // 初始化 states 的第一行資料
            sum += grid[0][i];
            states[0][i] = sum;
 }
        sum = 0;
 for(int j=0; j<m; j++){ // 初始化 states 的第一列資料
            sum += grid[j][0];
            states[j][0] = sum;
 }
 // 分階段求解，下層狀態的值是基于上一層狀態來的
 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++ 代碼，

// 狀態轉移方程
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
// 對應 leetcode64. 最小路徑和
class Solution { // 狀態轉移方程法
private:
    int minDist(int i, int j, vector<vector<int> >& matrix, vector<vector<int> >& mem) { // 呼叫minDist(n-1, n-1);
 if (i == 0 && j == 0) return matrix[0][0];
 if (mem[i][j] > 0) return mem[i][j];
        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<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > mem(m, vector<int>(n, -1));
 return minDist(m - 1, n - 1, grid, mem);
 }
};

三，四種演算法比較分析

如果將這四種演算法思想分一下類，那貪心、回溯、動態規劃可以歸為一類，而分治單獨可以作為一類，因為它跟其他三個都不大一樣，為什么這么說呢？因為前三個演算法解決問題的模型，都可以抽象成多階段決策最優解模型，而分治演算法解決的問題盡管大部分也是最優解問題，但是，大部分都不能抽象成多階段決策模型，

盡管動態規劃比回溯演算法高效，但是，并不是所有問題，都可以用動態規劃來解決，能用動態規劃解決的問題，需要滿足三個特征，最優子結構、無后效性和重復子問題，在重復子問題這一點上，動態規劃和分治演算法的區分非常明顯，分治演算法要求分割成的子問題，不能有重復子問題，而動態規劃正好相反，動態規劃之所以高效，就是因為回溯演算法實作中存在大量的重復子問題，

貪心演算法實際上是動態規劃演算法的一種特殊情況，它解決問題起來更加高效，代碼實作也更加簡潔，不過，它可以解決的問題也更加有限，它能解決的問題需要滿足三個條件，最優子結構、無后效性和貪心選擇性（這里我們不怎么強調重復子問題），其中，最優子結構、無后效性跟動態規劃中的無異，“貪心選擇性”的意思是，通過區域最優的選擇，能產生全域的最優選擇，每一個階段，我們都選擇當前看起來最優的決策，所有階段的決策完成之后，最終由這些區域最優解構成全域最優解，

四，內容總結

什么樣的問題適合用動態規劃解決？這些問題可以總結概括為“一個模型三個特征”，其中，“一個模型”指的是，問題可以抽象成分階段決策最優解模型，“三個特征”指的是最優子結構、無后效性和重復子問題，

哪兩種動態規劃的解題思路？它們分別是狀態轉移表法和狀態轉移方程法，其中，狀態轉移表法解題思路大致可以概括為，回溯演算法實作 - 定義狀態 - 畫遞回樹 - 找重復子問題 - 畫狀態轉移表 - 根據遞推關系填表 - 將填表程序翻譯成代碼，狀態轉移方程法的大致思路可以概括為，找最優子結構 - 寫狀態轉移方程 - 將狀態轉移方程翻譯成代碼，

練習題

假設我們有幾種不同幣值的硬幣 v1，v2，……，vn（單位是元），如果我們要支付 w 元，求最少需要多少個硬幣，比如，我們有 3 種不同的硬幣，1 元、3 元、5 元，我們要支付 9 元，最少需要 3 個硬幣（3 個 3 元的硬幣），

參考資料

動態規劃理論：一篇文章帶你徹底搞懂最優子結構、無后效性和重復子問題

點擊關注，第一時間了解華為云新鮮技術~

標籤：其他

上一篇：AI降臨，前端啟用面壁計劃

下一篇：返回列表