C++DP解題思路

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

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

14.3.1   問題判斷

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

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

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

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

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

相應(yīng)地，也存在一些“減分項(xiàng)”。

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

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

14.3.2   問題求解步驟

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

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

圖 14-10 展示了一個(gè)例子，給定網(wǎng)格的最小路徑和為 $13$ 。

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

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

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

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

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

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

第二步：找出最優(yōu)子結(jié)構(gòu)，進(jìn)而推導(dǎo)出狀態(tài)轉(zhuǎn)移方程

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

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

圖 14-12   最優(yōu)子結(jié)構(gòu)與狀態(tài)轉(zhuǎn)移方程

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

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

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

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

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

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]$ 。
• 終止條件：當(dāng) $i=0$ 且 $j=0$ 時(shí)，返回代價(jià) $grid[0,0]$ 。
• 剪枝：當(dāng) $i<0$ 時(shí)或 $j<0$ 時(shí)索引越界，此時(shí)返回代價(jià) $+\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];
    }
    // 若行列索引越界，則返回 +∞ 代價(jià)
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // 計(jì)算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價(jià)
    int left = minPathSumDFS(grid, i - 1, j);
    int up = minPathSumDFS(grid, i, j - 1);
    // 返回從左上角到 (i, j) 的最小路徑代價(jià)
    return min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}

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

本質(zhì)上看，造成重疊子問題的原因?yàn)椋?strong>存在多條路徑可以從左上角到達(dá)某一單元格。

圖 14-14   暴力搜索遞歸樹

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

2.   方法二：記憶化搜索

我們引入一個(gè)和網(wǎng)格 grid 相同尺寸的記憶列表 mem ，用于記錄各個(gè)子問題的解，并將重疊子問題進(jìn)行剪枝。

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

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

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

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

基于迭代實(shí)現(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)轉(zhuǎn)移：首行
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // 狀態(tài)轉(zhuǎn)移：首列
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // 狀態(tài)轉(zhuǎn)移：其余行列
    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)轉(zhuǎn)移過程，其遍歷了整個(gè)網(wǎng)格，因此時(shí)間復(fù)雜度為 $O(nm)$ 。

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

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

4.   空間優(yōu)化

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

請注意，因?yàn)閿?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)轉(zhuǎn)移：首行
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 狀態(tài)轉(zhuǎn)移：其余行
    for (int i = 1; i < n; i++) {
        // 狀態(tài)轉(zhuǎn)移：首列
        dp[0] = dp[0] + grid[i][0];
        // 狀態(tài)轉(zhuǎn)移：其余列
        for (int j = 1; j < m; j++) {
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}