C++DP解題思路

上兩節(jié)介紹了動態(tài)規(guī)劃問題的主要特征，接下來我們一起探究兩個更加實用的問題。

1. 如何判斷一個問題是不是動態(tài)規(guī)劃問題？
2. 求解動態(tài)規(guī)劃問題該從何處入手，完整步驟是什么？

14.3.1   問題判斷

總的來說，如果一個問題包含重疊子問題、最優(yōu)子結構，并滿足無后效性，那么它通常就適合用動態(tài)規(guī)劃求解。然而，我們很難從問題描述上直接提取出這些特性。因此我們通常會放寬條件，先觀察問題是否適合使用回溯（窮舉）解決。

適合用回溯解決的問題通常滿足“決策樹模型”，這種問題可以使用樹形結構來描述，其中每一個節(jié)點代表一個決策，每一條路徑代表一個決策序列。

換句話說，如果問題包含明確的決策概念，并且解是通過一系列決策產生的，那么它就滿足決策樹模型，通常可以使用回溯來解決。

在此基礎上，動態(tài)規(guī)劃問題還有一些判斷的“加分項”。

• 問題包含最大（小）或最多（少）等最優(yōu)化描述。
• 問題的狀態(tài)能夠使用一個列表、多維矩陣或樹來表示，并且一個狀態(tài)與其周圍的狀態(tài)存在遞推關系。

相應地，也存在一些“減分項”。

• 問題的目標是找出所有可能的解決方案，而不是找出最優(yōu)解。
• 問題描述中有明顯的排列組合的特征，需要返回具體的多個方案。

如果一個問題滿足決策樹模型，并具有較為明顯的“加分項“，我們就可以假設它是一個動態(tài)規(guī)劃問題，并在求解過程中驗證它。

14.3.2   問題求解步驟

動態(tài)規(guī)劃的解題流程會因問題的性質和難度而有所不同，但通常遵循以下步驟：描述決策，定義狀態(tài)，建立 $dp$ 表，推導狀態(tài)轉移方程，確定邊界條件等。

為了更形象地展示解題步驟，我們使用一個經典問題“最小路徑和”來舉例。

圖 14-10 展示了一個例子，給定網格的最小路徑和為 $13$ 。

圖 14-10   最小路徑和示例數(shù)據(jù)

第一步：思考每輪的決策，定義狀態(tài)，從而得到 $dp$ 表

本題的每一輪的決策就是從當前格子向下或向右一步。設當前格子的行列索引為 $[i,j]$ ，則向下或向右走一步后，索引變?yōu)?$[i+1,j]$ 或 $[i,j+1]$ 。因此，狀態(tài)應包含行索引和列索引兩個變量，記為 $[i,j]$ 。

狀態(tài) $[i,j]$ 對應的子問題為：從起始點 $[0,0]$ 走到 $[i,j]$ 的最小路徑和，解記為 $dp[i,j]$ 。

至此，我們就得到了圖 14-11 所示的二維 $dp$ 矩陣，其尺寸與輸入網格 $grid$ 相同。

圖 14-11   狀態(tài)定義與 dp 表

第二步：找出最優(yōu)子結構，進而推導出狀態(tài)轉移方程

對于狀態(tài) $[i,j]$ ，它只能從上邊格子 $[i?1,j]$ 和左邊格子 $[i,j?1]$ 轉移而來。因此最優(yōu)子結構為：到達 $[i,j]$ 的最小路徑和由 $[i,j?1]$ 的最小路徑和與 $[i?1,j]$ 的最小路徑和，這兩者較小的那一個決定。

根據(jù)以上分析，可推出圖 14-12 所示的狀態(tài)轉移方程：

圖 14-12   最優(yōu)子結構與狀態(tài)轉移方程

第三步：確定邊界條件和狀態(tài)轉移順序

在本題中，首行的狀態(tài)只能從其左邊的狀態(tài)得來，首列的狀態(tài)只能從其上邊的狀態(tài)得來，因此首行 $i=0$ 和首列 $j=0$ 是邊界條件。

如圖 14-13 所示，由于每個格子是由其左方格子和上方格子轉移而來，因此我們使用采用循環(huán)來遍歷矩陣，外循環(huán)遍歷各行、內循環(huán)遍歷各列。

圖 14-13   邊界條件與狀態(tài)轉移順序

根據(jù)以上分析，我們已經可以直接寫出動態(tài)規(guī)劃代碼。然而子問題分解是一種從頂至底的思想，因此按照“暴力搜索 $\to$ 記憶化搜索 $\to$ 動態(tài)規(guī)劃”的順序實現(xiàn)更加符合思維習慣。

1.   方法一：暴力搜索

從狀態(tài) $[i,j]$ 開始搜索，不斷分解為更小的狀態(tài) $[i?1,j]$ 和 $[i,j?1]$ ，遞歸函數(shù)包括以下要素。

• 遞歸參數(shù)：狀態(tài) $[i,j]$ 。
• 返回值：從 $[0,0]$ 到 $[i,j]$ 的最小路徑和 $dp[i,j]$ 。
• 終止條件：當 $i=0$ 且 $j=0$ 時，返回代價 $grid[0,0]$ 。
• 剪枝：當 $i<0$ 時或 $j<0$ 時索引越界，此時返回代價 $+\mathrm{\infty }$ ，代表不可行。

min_path_sum.cpp

/* 最小路徑和：暴力搜索 */
int minPathSumDFS(vector<vector<int>> &grid, int i, int j) {
    // 若為左上角單元格，則終止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，則返回 +∞ 代價
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
    int left = minPathSumDFS(grid, i - 1, j);
    int up = minPathSumDFS(grid, i, j - 1);
    // 返回從左上角到 (i, j) 的最小路徑代價
    return min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}

圖 14-14 給出了以 $dp[2,1]$ 為根節(jié)點的遞歸樹，其中包含一些重疊子問題，其數(shù)量會隨著網格 grid 的尺寸變大而急劇增多。

本質上看，造成重疊子問題的原因為：存在多條路徑可以從左上角到達某一單元格。

圖 14-14   暴力搜索遞歸樹

每個狀態(tài)都有向下和向右兩種選擇，從左上角走到右下角總共需要 $m+n?2$ 步，所以最差時間復雜度為 $O(2^{m+n})$ 。請注意，這種計算方式未考慮臨近網格邊界的情況，當?shù)竭_網絡邊界時只剩下一種選擇。因此實際的路徑數(shù)量會少一些。

2.   方法二：記憶化搜索

我們引入一個和網格 grid 相同尺寸的記憶列表 mem ，用于記錄各個子問題的解，并將重疊子問題進行剪枝。

min_path_sum.cpp

/* 最小路徑和：記憶化搜索 */
int minPathSumDFSMem(vector<vector<int>> &grid, vector<vector<int>> &mem, int i, int j) {
    // 若為左上角單元格，則終止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，則返回 +∞ 代價
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // 若已有記錄，則直接返回
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // 左邊和上邊單元格的最小路徑代價
    int left = minPathSumDFSMem(grid, mem, i - 1, j);
    int up = minPathSumDFSMem(grid, mem, i, j - 1);
    // 記錄并返回左上角到 (i, j) 的最小路徑代價
    mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
    return mem[i][j];
}

如圖 14-15 所示，在引入記憶化后，所有子問題的解只需計算一次，因此時間復雜度取決于狀態(tài)總數(shù)，即網格尺寸 $O(nm)$ 。

圖 14-15   記憶化搜索遞歸樹

3.   方法三：動態(tài)規(guī)劃

基于迭代實現(xiàn)動態(tài)規(guī)劃解法。

min_path_sum.cpp

/* 最小路徑和：動態(tài)規(guī)劃 */
int minPathSumDP(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    // 初始化 dp 表
    vector<vector<int>> dp(n, vector<int>(m));
    dp[0][0] = grid[0][0];
    // 狀態(tài)轉移：首行
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // 狀態(tài)轉移：首列
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // 狀態(tài)轉移：其余行列
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}

圖 14-16 展示了最小路徑和的狀態(tài)轉移過程，其遍歷了整個網格，因此時間復雜度為 $O(nm)$ 。

數(shù)組 dp 大小為 $n\times m$ ，因此空間復雜度為 $O(nm)$ 。

圖 14-16   最小路徑和的動態(tài)規(guī)劃過程

4.   空間優(yōu)化

由于每個格子只與其左邊和上邊的格子有關，因此我們可以只用一個單行數(shù)組來實現(xiàn) $dp$ 表。

請注意，因為數(shù)組 dp 只能表示一行的狀態(tài)，所以我們無法提前初始化首列狀態(tài)，而是在遍歷每行中更新它。

min_path_sum.cpp

/* 最小路徑和：空間優(yōu)化后的動態(tài)規(guī)劃 */
int minPathSumDPComp(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    // 初始化 dp 表
    vector<int> dp(m);
    // 狀態(tài)轉移：首行
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 狀態(tài)轉移：其余行
    for (int i = 1; i < n; i++) {
        // 狀態(tài)轉移：首列
        dp[0] = dp[0] + grid[i][0];
        // 狀態(tài)轉移：其余列
        for (int j = 1; j < m; j++) {
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}