算法學習筆記（8.2）-動態規劃入門進階

問題判斷:

問題求解步驟：

圖例：

解析：

方法一：暴力搜索

實現代碼如下所示：

解析：

方法二：記憶化搜索

代碼示例：

解析：

方法三：動態規劃

空間優化

代碼如下

問題判斷:

總的來說，如果一個問題包含重疊子問題、最優子結構，并滿足無后效性，那么它通常適合用動態規劃求解。然而，我們很難從問題的描述中直接提取出這些特征，因此通常需要放寬條件，首先需要觀察問題適不適合使用回溯（窮舉）解決。

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

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

在此基礎上，動態規劃問題還有一些判斷的“加分項”。

1. 問題包含最大（小）或最多（少）等優化描述。

2. 問題的狀態能夠使用一個列表、多維矩陣或樹來表示，并且一個狀態與其周圍的狀態存在遞推關系。

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

1. 問題的目標是找出所有的解決方案，而不是找出最優解。

2. 問題描述中有明顯的排列組合特征，需要返回具體的對個方案。

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

問題求解步驟：

動態規劃的問題解題流程會因為問題的性質和難度有所不同，但通常遵循一下步驟：描述決策，定義狀態，建立dp表，推導狀態轉移方程，確定邊界問題等。

為了理解動態規劃的解題的過程，使用一個經典的例題“最短路徑和”

Question：

給定一個n * m的二維網格grid，網格中的每個單元包含一個非負整數，表示該單元格的代價。機器人以左上角單元格為起始點，每次只能向下或者向右移動一步，直至到達右下角單元格。請返回左上角到右下角的最小路徑和。

圖例：

給定網格的最小路徑和為13

第一步：思考每輪的決策，定義狀態，從而得到dp表

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

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

如圖所示：dp二維矩陣，其尺寸與輸入網格grid相同。

注意點：（Note）

動態規劃和回溯過程可以描述成為一個決策序列，而狀態由所有決策變量構成。應當包含描述解題進度的所有變量，其包含了足夠的信息，能用來推導下一個狀態。

每個狀態都對應一個子問題，我們會定義成為一個dp表來存儲所有子問題的解，狀態的每個獨立變量都是dp表中的一個維度。從本質上看，dp表是狀態和子問題的解之間的映射。

第二步：找出最優子結構，進而推導出狀態轉移方程

對應狀態[i,j]，它只能從上邊的格子[i-1，j]和左邊的格子[I,j-1]轉移過來。因此最優子結構為：到達[i,j]的最小路徑和由[i-1，j]的最小路徑和與[I,j-1的最小路徑和哪個較小來決定。

根據以上的分析得出狀態轉移方程為：

dp[i,j] = min(dp[i-1,j],dp[i,j-1]) +grid[i,j]

圖示如下：

注意點：（Note）

根據定義好的dp表，思考原問題和子問題的關系，找出通過子問題的最優解來構造原問題的最優解的方法，即最優子結構。

一旦我們找到了最優子結構，就可以使用它來構建出來狀態轉移方程。

第三步：確定邊界條件和狀態轉移順序

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

如圖所示，由于每個格子是由其左方格子和上方格子轉移而來，因此我們使用循環來遍歷矩陣，外循環遍歷各行，內循環遍歷各列。

解析：

根據對上面的理解我們已經可以寫出動態規劃的代碼。然而子問題的解決是一種從頂至底的思想，因此按照“暴力搜索”->“記憶化搜索”->“動態規劃”的順序實現符合思維習慣。

方法一：暴力搜索

從狀態[i,j]開始搜索，不斷分解為更小的狀態[i-1,j]和[i,j-1]，遞歸函數包括以下的要素。

遞歸參數：狀態[i,j]。
返回值：從[0,0]到[i,j]的最小路徑和dp[i,j]。
終止條件：當 i = 0 且 j = 0 時，返回代價grid[0,0]。
剪枝：當i<0時或j<0時索引越界時，此時返回代價+∞，代表不可行。

實現代碼如下所示：

# python 代碼示例
def min_path_sum_dfs(grid, i, j) :if i == 0 and j == 0 :return grid[0][0]if i < 0 or j < 0 :return infup = min_path_sum_dfs(grid, i - 1, j)left = min_path_sum_dfs(grid, i, j - 1)return min(up, left) + grid[i][j]

// c++ 代碼示例
int minPathSumDFS(vector<vector<int>> &grid, int i, int j)
{if (i == 0 && j == 0){return grid[0][0] ;}    if (i < 0 or j < 0){retunr INT_MAX ;}int up = minPathSumDFS(grid, i - 1, j) ;int left = minPathSumDFS(grid, i, j - 1) ;return min(up, left) + gird[i][j] ;
}

解析：

給出一個dp[2,1]為根節點的遞歸樹，其中包含一些重疊子問題，其數量會隨著網格grid的尺寸變大而急劇增多。

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

每個狀態都有向下和向右兩種選擇，從左上角走到右下角總共需要m+n-2步，所以最差的時間復雜度為O(2^(m+n))。這種計算方法并沒有考慮網格的邊界情況，當到達網格邊界時只剩下一種選擇，因此實際的路徑會少一些。

方法二：記憶化搜索

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

代碼示例：

// c++ 代碼示例
def min_path_sum_dfs_mem(grid, mem, i, j) :if i == 0 and j == 0 :return grid[0][0]if i < 0 or j < 0 :return infif mem[i][j] != -1 :return mem[i][j]up = min_path_sum_dfs_mem(grid, mem, i - 1, j)left = min_path_sum_dfs_mem(grid, mem, i, j - 1)mem[i][j] = min(up, left) + grid[i][j]return mem[i][j]

// c++ 代碼示例
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 up = minPathSumDFSMem(grid, mem, i - 1, j) ; int left = minPathSumDFSMem(grid, mem, i, j - 1) ;mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX ;return mem[i][j] ;
}

解析：

在引入記憶化搜索之后，所有的子問題只需要計算一次，因此時間復雜度取決于狀態總數，即網格尺寸O(m*n)

方法三：動態規劃

基于迭代實現動態規劃，代碼如下所示：

# pyhton 代碼示例
def min_path_sum_dp(grid) :n, m = len(grid), len(grid[0])dp = [ [0] * m for _ in range(n)]dp[0][0] = grid[0][0]for j in range(1, m) :dp[0][j] = dp[0][j - 1] + grid[0][j]for i in range(1, n) :dp[i][0] = dp[i - 1][0] + grid[i][0]for i in range(1, n) :for j in range(1, m) :dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + gird[i][j]return dp[n - 1][m - 1]

int minPathSumDP(vector<vector<int>> &grid) {int n = grid.size(), m = grid[0].size();vector<vector<int>> dp(n, vector<int>(m));dp[0][0] = grid[0][0];for (int j = 1; j < m; j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}for (int i = 1; i < n; i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}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];
}

動態規劃的過程如下所示：便利了整個網絡，因此時間復雜度為O(m*n)。

數組的dp的大小也為m * n ,因此空間復雜度為O(m*n)。

空間優化

由于每個格子只與左邊和上邊的格子有關，我們可以只用一個單行數組來實現dp表。

關鍵：數組dp只能表示一行的狀態，我們無法提前初始化首行的狀態，而是在遍歷每行時更新它。

代碼如下：

# python 代碼示例def min_path_sum_dp_comp(grid : list[list[int]]) -> int :n, m = len(grid), len(grid[0])dp = [0] * mdp[0] = grid[0][0]for j in range(1, m) :dp[j] = dp[j - 1] + grid[0][j]for i in range(1, n) :dp[0] = dp[0] + grid[i][0]for j in range(1, m) :dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]return dp[m - 1]

// c++ 代碼示例
int minPathSumDPComp(vector<vector<int>> &grid)
{int n = grid.size(), m = grid[0].size() ;vector<int> dp(m) ;dp[0] = grid[0][0] ;for (int j = 1 ; j < m ; j++){dp[j] = dp[j - 1] + gird[0][j] ;}for (int i = 1 ; i < n ; i++){dp[0] = dp[0] + grid[i][0] ;for (int j = 1 ; j < m ; j++){dp[j] = min(dp[j - 1], dp[j]) + grid[i][j] ;}}return dp[m- 1] ;
}