深入淺出動態規劃演算法(中)

語言: CN / TW / HK

開啟掘金成長之旅!這是我參與「掘金日新計劃 · 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),其中 ij 分別表示行和列,dist 表示從起點到達 (i, j) 的路徑長度。從圖中,可以看出,儘管 (i, j, dist) 不存在重複,但是 (i, j) 重複的有很多。對於 (i, j) 重複的節點,我們只需要選擇 dist 最小的節點,繼續遞迴求解,其他節點就可以捨棄了。

最小問題的遞迴樹

2,動態規劃解法的 C++ 程式碼如下:

```cpp // 對應 leetcode64. 最小路徑和 class Solution { // 動態規劃:狀態轉移表法 public: int minPathSum(vector>& grid) { int m = grid.size(); int n = grid[0].size(); vector > states(m, vector(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];
}

}; ```

leetcode64 動態規劃解法程式碼提交記錄

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 >& matrix, vector >& 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>& grid) { int m = grid.size(); int n = grid[0].size(); vector > mem(m, vector(n, -1));

    return minDist(m - 1, n - 1, grid, mem);
}

}; ```

leetcode64 動態規劃解法程式碼提交記錄

三,四種演算法比較分析

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

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

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

四,內容總結

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

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

練習題

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

參考資料

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