14.3 動態規劃解題思路¶
上兩節介紹了動態規劃問題的主要特徵,接下來我們一起探究兩個更加實用的問題。
- 如何判斷一個問題是不是動態規劃問題?
- 求解動態規劃問題該從何處入手,完整步驟是什麼?
14.3.1 問題判斷¶
總的來說,如果一個問題包含重疊子問題、最優子結構,並滿足無後效性,那麼它通常適合用動態規劃求解。然而,我們很難從問題描述中直接提取出這些特性。因此我們通常會放寬條件,先觀察問題是否適合使用回溯(窮舉)解決。
適合用回溯解決的問題通常滿足“決策樹模型”,這種問題可以使用樹形結構來描述,其中每一個節點代表一個決策,每一條路徑代表一個決策序列。
換句話說,如果問題包含明確的決策概念,並且解是透過一系列決策產生的,那麼它就滿足決策樹模型,通常可以使用回溯來解決。
在此基礎上,動態規劃問題還有一些判斷的“加分項”。
- 問題包含最大(小)或最多(少)等最佳化描述。
- 問題的狀態能夠使用一個串列、多維矩陣或樹來表示,並且一個狀態與其周圍的狀態存在遞推關係。
相應地,也存在一些“減分項”。
- 問題的目標是找出所有可能的解決方案,而不是找出最優解。
- 問題描述中有明顯的排列組合的特徵,需要返回具體的多個方案。
如果一個問題滿足決策樹模型,並具有較為明顯的“加分項”,我們就可以假設它是一個動態規劃問題,並在求解過程中驗證它。
14.3.2 問題求解步驟¶
動態規劃的解題流程會因問題的性質和難度而有所不同,但通常遵循以下步驟:描述決策,定義狀態,建立 \(dp\) 表,推導狀態轉移方程,確定邊界條件等。
為了更形象地展示解題步驟,我們使用一個經典問題“最小路徑和”來舉例。
Question
給定一個 \(n \times m\) 的二維網格 grid ,網格中的每個單元格包含一個非負整數,表示該單元格的代價。機器人以左上角單元格為起始點,每次只能向下或者向右移動一步,直至到達右下角單元格。請返回從左上角到右下角的最小路徑和。
圖 14-10 展示了一個例子,給定網格的最小路徑和為 \(13\) 。
圖 14-10 最小路徑和示例資料
圖解 14-10:四乘四網格的最小路徑和
在 4×4 代價網格中從左上角只向右或向下走到右下角,綠色最優路徑的七格總和為 13。
給定一個 4×4 的非負整數網格 grid,每個單元格的數值代表經過該格所需支付的代價。從左上角起點 [0, 0] 出發,每次只能向右或向下移動一格,直至到達右下角終點 [3, 3],起點和終點的數值均計入路徑總和(行列索引從 0 開始)。
左側展示完整的 4×4 輸入網格,並在左上角標註“起點”、右下角標註“終點”;中央向右箭頭指向右側同一個 4×4 網格,其中一條從左上到右下的七格折線路徑以綠色高亮,圖下方標註“最小路徑和為 13,對應最佳方案為 1→2→2→3→2→1→2”。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
右側綠色最優路徑從起點 [0, 0](值為 1)出發,先向下到 [1, 0](值為 2),再向右到 [1, 1](值為 2),接著向下到 [2, 1](值為 3),隨後連續兩次向右經過 [2, 2](值為 2)和 [2, 3](值為 1),最後向下到達終點 [3, 3](值為 2),沿途代價相加為 1+2+2+3+2+1+2=13。
第一步:思考每輪的決策,定義狀態,從而得到 \(dp\) 表
本題的每一輪的決策就是從當前格子向下或向右走一步。設當前格子的行列索引為 \([i, j]\) ,則向下或向右走一步後,索引變為 \([i+1, j]\) 或 \([i, j+1]\) 。因此,狀態應包含行索引和列索引兩個變數,記為 \([i, j]\) 。
狀態 \([i, j]\) 對應的子問題為:從起始點 \([0, 0]\) 走到 \([i, j]\) 的最小路徑和,解記為 \(dp[i, j]\) 。
至此,我們就得到了圖 14-11 所示的二維 \(dp\) 矩陣,其尺寸與輸入網格 \(grid\) 相同。
圖 14-11 狀態定義與 dp 表
圖解 14-11:把網格位置定義為二維 dp 狀態
用行列座標 [i, j] 定義狀態,建立同尺寸 4×4 二維 dp 表對應從起點到各格的最小路徑和子問題。
輸入為 4×4 非負代價網格 grid(行列索引 0 至 3 的完整數值見表),從左上角起點 [0, 0] 出發每次只能向右或向下走一格,起點與終點均計入路徑和。本圖對比原網格 grid 與動態規劃表 dp 的狀態定義。
首先區分兩個 4×4 矩陣的含義:grid[i, j] 僅記錄經過單個格子的代價,而 dp[i, j] 記錄從左上角起點 [0, 0] 走到格子 [i, j](含首尾兩格)的累計最小路徑和。例如 grid[1, 1] = 2 只代表該格自身的單格代價,不能直接當作累計路徑和 dp[1, 1](後者還包含從起點到達該格的路徑代價)。
圖中在 grid 旁標出行索引 i、i+1 與列索引 j、j+1,並以當前格 [1, 1](代價 2)演示每輪移動決策:向右走一格列索引加 1,到達 [1, 2](即 [i, j+1]),該格代價為 4;向下走一格行索引加 1,到達 [2, 1](即 [i+1, j]),該格代價為 3。每次移動只改變行或列中的一個座標,因此用二維行列索引 [i, j] 定義狀態。
右側 dp 表是與 grid 尺寸相同的 4×4 矩陣,行列索引均為 0 至 3,單元格依次記作 dp[0, 0] 至 dp[3, 3],分別對應到達各格的最小路徑和子問題。本圖只建立狀態定義與座標對映,尚未計算和填寫具體路徑和數值。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
圖底部依次列出四項建模定義:決策是每輪向右或向下走一格;狀態是所在格子的行列索引 [i,j];子問題是從左上角 [0,0] 到達 [i,j] 的最小路徑和;dp 表是記錄所有這些子問題解的二維矩陣。
Note
動態規劃和回溯過程可以描述為一個決策序列,而狀態由所有決策變數構成。它應當包含描述解題進度的所有變數,其包含了足夠的資訊,能夠用來推導出下一個狀態。
每個狀態都對應一個子問題,我們會定義一個 \(dp\) 表來儲存所有子問題的解,狀態的每個獨立變數都是 \(dp\) 表的一個維度。從本質上看,\(dp\) 表是狀態和子問題的解之間的對映。
第二步:找出最優子結構,進而推導出狀態轉移方程
對於狀態 \([i, j]\) ,它只能從上邊格子 \([i-1, j]\) 和左邊格子 \([i, j-1]\) 轉移而來。因此最優子結構為:到達 \([i, j]\) 的最小路徑和由 \([i, j-1]\) 的最小路徑和與 \([i-1, j]\) 的最小路徑和中較小的那一個決定。
根據以上分析,可推出圖 14-12 所示的狀態轉移方程:
圖 14-12 最優子結構與狀態轉移方程
圖解 14-12:最小路徑和的狀態轉移
到達內部格子的最後一步只能來自上方或左方,取兩處累計最小路徑和的較小值再加當前格代價。
在非負數字網格中,從左上角 [0, 0] 出發,每次只能向右或向下移動一格,沿途所有格子的數值(含起點和終點)累加為路徑和。記 dp[i, j] 為從起點到達第 i 行、第 j 列格子的最小路徑和,行列索引均從 0 開始;本例的 4×4 輸入網格見表。
左圖為 4×4 原始代價網格 grid,右圖為同尺寸的符號 dp 表,各格僅標出狀態名 dp[0, 0] 至 dp[3, 3]。左圖將當前格 [2, 2](值為 2)塗成綠色,將其上方相鄰格 [1, 2](值為 4)塗成紫色、左方相鄰格 [2, 1](值為 3)塗成藍色;右表用相同顏色高亮對應的 dp[2, 2]、dp[1, 2] 與 dp[2, 1]。
右表中一條向下箭頭從 dp[1, 2] 指向 dp[2, 2],一條向右箭頭從 dp[2, 1] 指向 dp[2, 2]。圖下方寫出狀態轉移方程 dp[i, j] = min(dp[i-1, j], dp[i, j-1]) + grid[i, j];注意方程中的 min 比較的是到達兩個前驅格的累計最小路徑和,而不是左圖原始網格里的單格代價 4 和 3。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
以圖中綠色高亮的內部格 i=2、j=2 為例,只能從上方 [1, 2] 向下走一格、或從左方 [2, 1] 向右走一格到達該格,因此狀態轉移寫為 dp[2, 2] = min(dp[1, 2], dp[2, 1]) + grid[2, 2],其中 grid[2, 2]=2。右側 dp 表在此僅展示符號依賴關係,尚未填入具體累計數值。
Note
根據定義好的 \(dp\) 表,思考原問題和子問題的關係,找出透過子問題的最優解來構造原問題的最優解的方法,即最優子結構。
一旦我們找到了最優子結構,就可以使用它來構建出狀態轉移方程。
第三步:確定邊界條件和狀態轉移順序
在本題中,處在首行的狀態只能從其左邊的狀態得來,處在首列的狀態只能從其上邊的狀態得來,因此首行 \(i = 0\) 和首列 \(j = 0\) 是邊界條件。
如圖 14-13 所示,由於每個格子是由其左方格子和上方格子轉移而來,因此我們使用迴圈來走訪矩陣,外迴圈走訪各行,內迴圈走訪各列。
圖 14-13 邊界條件與狀態轉移順序
圖解 14-13:最小路徑和的邊界與填表順序
先設定起點並沿首行向右、首列向下累加初始化邊界,再按從上到下、從左到右的正序走訪內部格。
在非負數字網格中從 [0, 0] 出發只能向右或向下移動,起點與終點均計入路徑和,dp[i, j] 表示到達第 i 行、第 j 列的最小路徑和(行列索引 0 至 3)。本圖用左右兩個 4×4 符號 dp 表分別說明“邊界條件:初始化首行首列”與“狀態轉移順序:正序走訪矩陣”,不展示具體網格數值。
左圖用綠色標出左上角起點,藍色標出首行其餘格,紫色標出首列其餘格;箭頭分別沿首行向右、沿首列向下。右圖的箭頭表示內部格依賴已就緒的上方和左方狀態。兩表都僅寫 dp[0,0] 至 dp[3,3] 等符號。
先初始化起點,再沿唯一到達方向累加首行和首列。內部九格按外層行索引 i = 1、2、3,內層列索引 j = 1、2、3 正序填寫。這樣,求 dp[i,j] 時,上方 dp[i-1,j] 已在前一行算好,左方 dp[i,j-1] 已在本行左側算好。下表的計算公式據圖中的邊界和前驅關係整理,原圖沒有逐項寫出這些公式。
| 區域 | 索引範圍 | 前驅 | 計算方式 |
|---|---|---|---|
| 起點 | [0,0] | 無 | dp[0,0]=grid[0,0] |
| 首行 | [0,j],j=1、2、3 | [0,j-1] | dp[0,j]=dp[0,j-1]+grid[0,j] |
| 首列 | [i,0],i=1、2、3 | [i-1,0] | dp[i,0]=dp[i-1,0]+grid[i,0] |
| 內部 | i=1、2、3;各行 j=1、2、3 | [i-1,j] 和 [i,j-1] | dp[i,j]=min(dp[i-1,j],dp[i,j-1])+grid[i,j] |
首行與首列只有一個可用前驅,內部格才需要在上方與左方兩個前驅之間取最小值。
Note
邊界條件在動態規劃中用於初始化 \(dp\) 表,在搜尋中用於剪枝。
狀態轉移順序的核心是要保證在計算當前問題的解時,所有它依賴的更小子問題的解都已經被正確地計算出來。
根據以上分析,我們已經可以直接寫出動態規劃程式碼。然而子問題分解是一種從頂至底的思想,因此按照“暴力搜尋 \(\rightarrow\) 記憶化搜尋 \(\rightarrow\) 動態規劃”的順序實現更加符合思維習慣。
1. 方法一:暴力搜尋¶
從狀態 \([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\) 時索引越界,此時返回代價 \(+\infty\) ,代表不可行。
實現程式碼如下:
def min_path_sum_dfs(grid: list[list[int]], i: int, j: int) -> int:
"""最小路徑和:暴力搜尋"""
# 若為左上角單元格,則終止搜尋
if i == 0 and j == 0:
return grid[0][0]
# 若行列索引越界,則返回 +∞ 代價
if i < 0 or j < 0:
return inf
# 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
up = min_path_sum_dfs(grid, i - 1, j)
left = min_path_sum_dfs(grid, i, j - 1)
# 返回從左上角到 (i, j) 的最小路徑代價
return min(left, up) + grid[i][j]
/* 最小路徑和:暴力搜尋 */
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 up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
return min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}
/* 最小路徑和:暴力搜尋 */
int minPathSumDFS(int[][] grid, int i, int j) {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
int up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
return Math.min(left, up) + grid[i][j];
}
/* 最小路徑和:暴力搜尋 */
int MinPathSumDFS(int[][] grid, int i, int j) {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return int.MaxValue;
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
int up = MinPathSumDFS(grid, i - 1, j);
int left = MinPathSumDFS(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
return Math.Min(left, up) + grid[i][j];
}
/* 最小路徑和:暴力搜尋 */
func minPathSumDFS(grid [][]int, i, j int) int {
// 若為左上角單元格,則終止搜尋
if i == 0 && j == 0 {
return grid[0][0]
}
// 若行列索引越界,則返回 +∞ 代價
if i < 0 || j < 0 {
return math.MaxInt
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
up := minPathSumDFS(grid, i-1, j)
left := minPathSumDFS(grid, i, j-1)
// 返回從左上角到 (i, j) 的最小路徑代價
return int(math.Min(float64(left), float64(up))) + grid[i][j]
}
/* 最小路徑和:暴力搜尋 */
func minPathSumDFS(grid: [[Int]], i: Int, j: Int) -> Int {
// 若為左上角單元格,則終止搜尋
if i == 0, j == 0 {
return grid[0][0]
}
// 若行列索引越界,則返回 +∞ 代價
if i < 0 || j < 0 {
return .max
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
let up = minPathSumDFS(grid: grid, i: i - 1, j: j)
let left = minPathSumDFS(grid: grid, i: i, j: j - 1)
// 返回從左上角到 (i, j) 的最小路徑代價
return min(left, up) + grid[i][j]
}
/* 最小路徑和:暴力搜尋 */
function minPathSumDFS(grid, i, j) {
// 若為左上角單元格,則終止搜尋
if (i === 0 && j === 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Infinity;
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
const up = minPathSumDFS(grid, i - 1, j);
const left = minPathSumDFS(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
return Math.min(left, up) + grid[i][j];
}
/* 最小路徑和:暴力搜尋 */
function minPathSumDFS(
grid: Array<Array<number>>,
i: number,
j: number
): number {
// 若為左上角單元格,則終止搜尋
if (i === 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Infinity;
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
const up = minPathSumDFS(grid, i - 1, j);
const left = minPathSumDFS(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
return Math.min(left, up) + grid[i][j];
}
/* 最小路徑和:暴力搜尋 */
int minPathSumDFS(List<List<int>> grid, int i, int j) {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
// 在 Dart 中,int 型別是固定範圍的整數,不存在表示“無窮大”的值
return BigInt.from(2).pow(31).toInt();
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
int up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
return min(left, up) + grid[i][j];
}
/* 最小路徑和:暴力搜尋 */
fn min_path_sum_dfs(grid: &Vec<Vec<i32>>, i: i32, j: i32) -> i32 {
// 若為左上角單元格,則終止搜尋
if i == 0 && j == 0 {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if i < 0 || j < 0 {
return i32::MAX;
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
let up = min_path_sum_dfs(grid, i - 1, j);
let left = min_path_sum_dfs(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
std::cmp::min(left, up) + grid[i as usize][j as usize]
}
/* 最小路徑和:暴力搜尋 */
int minPathSumDFS(int grid[MAX_SIZE][MAX_SIZE], 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 up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回從左上角到 (i, j) 的最小路徑代價
return myMin(left, up) != INT_MAX ? myMin(left, up) + grid[i][j] : INT_MAX;
}
/* 最小路徑和:暴力搜尋 */
fun minPathSumDFS(grid: Array<IntArray>, i: Int, j: Int): Int {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0]
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Int.MAX_VALUE
}
// 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
val up = minPathSumDFS(grid, i - 1, j)
val left = minPathSumDFS(grid, i, j - 1)
// 返回從左上角到 (i, j) 的最小路徑代價
return min(left, up) + grid[i][j]
}
### 最小路徑和:暴力搜尋 ###
def min_path_sum_dfs(grid, i, j)
# 若為左上角單元格,則終止搜尋
return grid[i][j] if i == 0 && j == 0
# 若行列索引越界,則返回 +∞ 代價
return Float::INFINITY if i < 0 || j < 0
# 計算從左上角到 (i-1, j) 和 (i, j-1) 的最小路徑代價
up = min_path_sum_dfs(grid, i - 1, j)
left = min_path_sum_dfs(grid, i, j - 1)
# 返回從左上角到 (i, j) 的最小路徑代價
[left, up].min + grid[i][j]
end
視覺化執行
圖 14-14 給出了以 \(dp[2, 1]\) 為根節點的遞迴樹,其中包含一些重疊子問題,其數量會隨著網格 grid 的尺寸變大而急劇增多。
從本質上看,造成重疊子問題的原因為:存在多條路徑可以從左上角到達某一單元格。
圖 14-14 暴力搜尋遞迴樹
圖解 14-14:最小路徑和的重複遞迴
從 dp[2,1] 查詢前驅時,兩條呼叫路線都到達 dp[1,0],它的子樹被展開兩次,第二次是重複計算。
在非負數字網格中從 [0, 0] 出發只能向右或向下移動,dp[i, j] 表示到達第 i 行、第 j 列的最小路徑和(索引從 0 開始)。本圖以 dp[2, 1] 為根節點展示自頂向下的暴力搜尋遞迴樹,不給出具體網格權重;注意遞迴是反向查詢“上一行”與“上一列”前驅,方向與實際行走時的向下、向右相反。
有效內部狀態取兩個前驅返回值的較小值,再加當前格代價:dp[i, j] = min(dp[i-1, j], dp[i, j-1]) + grid[i, j]。起點返回 grid[0, 0],負索引越界時返回正無窮。
遞迴樹的左分支查上一行(路線記“上”),右分支查上一列(路線記“左”);這些路線詞表示網格前驅方向,不是樹在畫面上的左右位置。
從根 dp[2,1] 經 dp[1,1] 再到 dp[1,0],路線是“上→左”;經 dp[2,0] 再到 dp[1,0],路線是“左→上”。這對應右下方的原注“dp[i+1, j] 和 dp[i, j+1] 都依賴 dp[i, j]”:本例中 dp[2,0] 和 dp[1,1] 都依賴 dp[1,0]。
暴力搜尋不儲存已解狀態,所以兩次 dp[1,0] 都各自展開子節點 dp[0,0] 與 dp[1,-1]。負索引節點標有“剪枝:索引越界”,按程式碼返回正無窮,在最小值比較中排除非法前驅。
下方 4×4 符號 dp 表(行、列索引均為 0 至 3)以底色突出本次搜尋涉及的六種有效狀態:[0,0]、[0,1]、[1,0]、[1,1]、[2,0]、[2,1];其餘十格仍標有對應 dp 符號,未參與本次搜尋。下表按先進入節點、再查上方、再查左方的呼叫順序列出整棵遞迴樹,重複狀態用不同路線區分。
| 呼叫路線 | 狀態 | 處理或返回 | 子節點 |
|---|---|---|---|
| 根 | dp[2,1] | 取兩前驅較小值,加 grid[2,1] | 上:dp[1,1];左:dp[2,0] |
| 上 | dp[1,1] | 取兩前驅較小值,加 grid[1,1] | 上:dp[0,1];左:dp[1,0] |
| 上→上 | dp[0,1] | 取兩前驅較小值,加 grid[0,1] | 上:dp[-1,1];左:dp[0,0] |
| 上→上→上 | dp[-1,1] | 越界,返回正無窮 | 不展開 |
| 上→上→左 | dp[0,0] | 起點,返回 grid[0,0] | 不展開 |
| 上→左 | dp[1,0] | 取兩前驅較小值,加 grid[1,0] | 上:dp[0,0];左:dp[1,-1] |
| 上→左→上 | dp[0,0] | 起點,返回 grid[0,0] | 不展開 |
| 上→左→左 | dp[1,-1] | 越界,返回正無窮 | 不展開 |
| 左 | dp[2,0] | 取兩前驅較小值,加 grid[2,0] | 上:dp[1,0];左:dp[2,-1] |
| 左→上 | dp[1,0] | 取兩前驅較小值,加 grid[1,0] | 上:dp[0,0];左:dp[1,-1] |
| 左→上→上 | dp[0,0] | 起點,返回 grid[0,0] | 不展開 |
| 左→上→左 | dp[1,-1] | 越界,返回正無窮 | 不展開 |
| 左→左 | dp[2,-1] | 越界,返回正無窮 | 不展開 |
按表計數,共 13 個呼叫節點,其中起點 dp[0,0] 出現 3 次,負索引節點出現 4 次:dp[-1,1] 一次、dp[1,-1] 兩次、dp[2,-1] 一次。
每個狀態都有向下和向右兩種選擇,從左上角走到右下角總共需要 \(m + n - 2\) 步,所以最差時間複雜度為 \(O(2^{m + n})\) ,其中 \(n\) 和 \(m\) 分別為網格的行數和列數。請注意,這種計算方式未考慮臨近網格邊界的情況,當到達網格邊界時只剩下一種選擇,因此實際的路徑數量會少一些。
2. 方法二:記憶化搜尋¶
我們引入一個和網格 grid 相同尺寸的記憶串列 mem ,用於記錄各個子問題的解,並將重疊子問題進行剪枝:
def min_path_sum_dfs_mem(
grid: list[list[int]], mem: list[list[int]], i: int, j: int
) -> int:
"""最小路徑和:記憶化搜尋"""
# 若為左上角單元格,則終止搜尋
if i == 0 and j == 0:
return grid[0][0]
# 若行列索引越界,則返回 +∞ 代價
if i < 0 or j < 0:
return inf
# 若已有記錄,則直接返回
if 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)
# 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = min(left, up) + grid[i][j]
return mem[i][j]
/* 最小路徑和:記憶化搜尋 */
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);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
return mem[i][j];
}
/* 最小路徑和:記憶化搜尋 */
int minPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
// 若已有記錄,則直接返回
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);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = Math.min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路徑和:記憶化搜尋 */
int MinPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return int.MaxValue;
}
// 若已有記錄,則直接返回
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);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = Math.Min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路徑和:記憶化搜尋 */
func minPathSumDFSMem(grid, mem [][]int, i, j int) int {
// 若為左上角單元格,則終止搜尋
if i == 0 && j == 0 {
return grid[0][0]
}
// 若行列索引越界,則返回 +∞ 代價
if i < 0 || j < 0 {
return math.MaxInt
}
// 若已有記錄,則直接返回
if mem[i][j] != -1 {
return mem[i][j]
}
// 左邊和上邊單元格的最小路徑代價
up := minPathSumDFSMem(grid, mem, i-1, j)
left := minPathSumDFSMem(grid, mem, i, j-1)
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = int(math.Min(float64(left), float64(up))) + grid[i][j]
return mem[i][j]
}
/* 最小路徑和:記憶化搜尋 */
func minPathSumDFSMem(grid: [[Int]], mem: inout [[Int]], i: Int, j: Int) -> Int {
// 若為左上角單元格,則終止搜尋
if i == 0, j == 0 {
return grid[0][0]
}
// 若行列索引越界,則返回 +∞ 代價
if i < 0 || j < 0 {
return .max
}
// 若已有記錄,則直接返回
if mem[i][j] != -1 {
return mem[i][j]
}
// 左邊和上邊單元格的最小路徑代價
let up = minPathSumDFSMem(grid: grid, mem: &mem, i: i - 1, j: j)
let left = minPathSumDFSMem(grid: grid, mem: &mem, i: i, j: j - 1)
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = min(left, up) + grid[i][j]
return mem[i][j]
}
/* 最小路徑和:記憶化搜尋 */
function minPathSumDFSMem(grid, mem, i, j) {
// 若為左上角單元格,則終止搜尋
if (i === 0 && j === 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Infinity;
}
// 若已有記錄,則直接返回
if (mem[i][j] !== -1) {
return mem[i][j];
}
// 左邊和上邊單元格的最小路徑代價
const up = minPathSumDFSMem(grid, mem, i - 1, j);
const left = minPathSumDFSMem(grid, mem, i, j - 1);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = Math.min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路徑和:記憶化搜尋 */
function minPathSumDFSMem(
grid: Array<Array<number>>,
mem: Array<Array<number>>,
i: number,
j: number
): number {
// 若為左上角單元格,則終止搜尋
if (i === 0 && j === 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Infinity;
}
// 若已有記錄,則直接返回
if (mem[i][j] != -1) {
return mem[i][j];
}
// 左邊和上邊單元格的最小路徑代價
const up = minPathSumDFSMem(grid, mem, i - 1, j);
const left = minPathSumDFSMem(grid, mem, i, j - 1);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = Math.min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路徑和:記憶化搜尋 */
int minPathSumDFSMem(List<List<int>> grid, List<List<int>> mem, int i, int j) {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
// 在 Dart 中,int 型別是固定範圍的整數,不存在表示“無窮大”的值
return BigInt.from(2).pow(31).toInt();
}
// 若已有記錄,則直接返回
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);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路徑和:記憶化搜尋 */
fn min_path_sum_dfs_mem(grid: &Vec<Vec<i32>>, mem: &mut Vec<Vec<i32>>, i: i32, j: i32) -> i32 {
// 若為左上角單元格,則終止搜尋
if i == 0 && j == 0 {
return grid[0][0];
}
// 若行列索引越界,則返回 +∞ 代價
if i < 0 || j < 0 {
return i32::MAX;
}
// 若已有記錄,則直接返回
if mem[i as usize][j as usize] != -1 {
return mem[i as usize][j as usize];
}
// 左邊和上邊單元格的最小路徑代價
let up = min_path_sum_dfs_mem(grid, mem, i - 1, j);
let left = min_path_sum_dfs_mem(grid, mem, i, j - 1);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i as usize][j as usize] = std::cmp::min(left, up) + grid[i as usize][j as usize];
mem[i as usize][j as usize]
}
/* 最小路徑和:記憶化搜尋 */
int minPathSumDFSMem(int grid[MAX_SIZE][MAX_SIZE], int mem[MAX_SIZE][MAX_SIZE], 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);
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = myMin(left, up) != INT_MAX ? myMin(left, up) + grid[i][j] : INT_MAX;
return mem[i][j];
}
/* 最小路徑和:記憶化搜尋 */
fun minPathSumDFSMem(
grid: Array<IntArray>,
mem: Array<IntArray>,
i: Int,
j: Int
): Int {
// 若為左上角單元格,則終止搜尋
if (i == 0 && j == 0) {
return grid[0][0]
}
// 若行列索引越界,則返回 +∞ 代價
if (i < 0 || j < 0) {
return Int.MAX_VALUE
}
// 若已有記錄,則直接返回
if (mem[i][j] != -1) {
return mem[i][j]
}
// 左邊和上邊單元格的最小路徑代價
val up = minPathSumDFSMem(grid, mem, i - 1, j)
val left = minPathSumDFSMem(grid, mem, i, j - 1)
// 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = min(left, up) + grid[i][j]
return mem[i][j]
}
### 最小路徑和:記憶化搜尋 ###
def min_path_sum_dfs_mem(grid, mem, i, j)
# 若為左上角單元格,則終止搜尋
return grid[0][0] if i == 0 && j == 0
# 若行列索引越界,則返回 +∞ 代價
return Float::INFINITY if i < 0 || j < 0
# 若已有記錄,則直接返回
return mem[i][j] if mem[i][j] != -1
# 左邊和上邊單元格的最小路徑代價
up = min_path_sum_dfs_mem(grid, mem, i - 1, j)
left = min_path_sum_dfs_mem(grid, mem, i, j - 1)
# 記錄並返回左上角到 (i, j) 的最小路徑代價
mem[i][j] = [left, up].min + grid[i][j]
end
視覺化執行
如圖 14-15 所示,在引入記憶化後,所有子問題的解只需計算一次,因此時間複雜度取決於狀態總數,即網格尺寸 \(O(nm)\) 。
圖 14-15 記憶化搜尋遞迴樹
圖解 14-15:最小路徑和的記憶化遞迴
第二次請求 dp[1,0] 時直接讀取快取的有效路徑和,不再展開子節點;這與越界返回正無窮的處理不同。
在非負數字網格中從 [0, 0] 出發只能向右或向下移動,dp[i, j] 表示到達第 i 行、第 j 列的最小路徑和(索引從 0 開始)。本圖同樣以 dp[2, 1] 為搜尋根,展示引入記憶化快取 mem 後對重疊子問題的剪枝效果,不展示具體網格權重。遞迴反向查詢上一行與上一列前驅,與實際行走時向下、向右的方向相反。
有效內部狀態取兩個前驅返回值的較小值,再加當前格代價:dp[i, j] = min(dp[i-1, j], dp[i, j-1]) + grid[i, j]。起點返回 grid[0, 0],負索引越界時返回正無窮。
遞迴樹的左分支查上一行(路線記“上”),右分支查上一列(路線記“左”);這些路線詞表示網格前驅方向,不是樹在畫面上的左右位置。
從根 dp[2,1] 經 dp[1,1] 再到 dp[1,0],路線是“上→左”;經 dp[2,0] 再到 dp[1,0],路線是“左→上”。兩條路線請求同一子問題。
先求解 dp[1,1] 分支:首次遇到 dp[1,0] 時,等待兩個前驅呼叫都返回,求出當前格最小路徑和並寫入 mem[1][0],隨後才返回 dp[1,1]。隨後求解 dp[2,0] 分支,再次請求 dp[1,0] 時命中“剪枝:已有記錄”,直接返回快取值,不再呼叫 dp[0,0] 和 dp[1,-1]。dp[2,0] 的另一個子節點 dp[2,-1](路線“左→左”)則是索引越界,返回正無窮;快取值仍是有效路徑和,參與最小值比較。
本次搜尋涉及行 0 至 2、列 0 至 1 的六種有效狀態:[0,0]、[0,1]、[1,0]、[1,1]、[2,0]、[2,1]。dp[0,1] 和首次求解的 dp[1,0] 各呼叫一次起點 dp[0,0],對應路線“上→上→左”和“上→左→上”。起點直接返回 grid[0,0],不讀寫 mem;因此保留兩個起點葉節點。下表按先進入節點、再查上方、再查左方的呼叫順序列出全部呼叫;本圖沒有另畫網格或 dp 表。
| 呼叫路線 | 狀態 | 處理或返回 | 子節點 |
|---|---|---|---|
| 根 | dp[2,1] | 取兩前驅較小值,加 grid[2,1],計算完成後存入 mem | 上:dp[1,1];左:dp[2,0] |
| 上 | dp[1,1] | 取兩前驅較小值,加 grid[1,1],計算完成後存入 mem | 上:dp[0,1];左:dp[1,0] |
| 上→上 | dp[0,1] | 取兩前驅較小值,加 grid[0,1],計算完成後存入 mem | 上:dp[-1,1];左:dp[0,0] |
| 上→上→上 | dp[-1,1] | 越界,返回正無窮 | 不展開 |
| 上→上→左 | dp[0,0] | 起點,返回 grid[0,0] | 不展開 |
| 上→左 | dp[1,0] | 取兩前驅較小值,加 grid[1,0],計算完成後存入 mem | 上:dp[0,0];左:dp[1,-1] |
| 上→左→上 | dp[0,0] | 起點,返回 grid[0,0] | 不展開 |
| 上→左→左 | dp[1,-1] | 越界,返回正無窮 | 不展開 |
| 左 | dp[2,0] | 取兩前驅較小值,加 grid[2,0],計算完成後存入 mem | 上:dp[1,0];左:dp[2,-1] |
| 左→上 | dp[1,0] | 命中快取,返回已求出的 dp[1,0] | 不展開 |
| 左→左 | dp[2,-1] | 越界,返回正無窮 | 不展開 |
省去第二次 dp[1,0] 的兩個子節點後,呼叫節點從暴力圖的 13 個減為 11 個。按表計數,保留 2 個起點 dp[0,0],以及 3 個越界節點 dp[-1,1]、dp[1,-1]、dp[2,-1]。
3. 方法三:動態規劃¶
基於迭代實現動態規劃解法,程式碼如下所示:
def min_path_sum_dp(grid: list[list[int]]) -> int:
"""最小路徑和:動態規劃"""
n, m = len(grid), len(grid[0])
# 初始化 dp 表
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][j - 1], dp[i - 1][j]) + grid[i][j]
return dp[n - 1][m - 1]
/* 最小路徑和:動態規劃 */
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];
// 狀態轉移:首行
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];
}
/* 最小路徑和:動態規劃 */
int minPathSumDP(int[][] grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
int[][] dp = new int[n][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] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路徑和:動態規劃 */
int MinPathSumDP(int[][] grid) {
int n = grid.Length, m = grid[0].Length;
// 初始化 dp 表
int[,] dp = new int[n, 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] = Math.Min(dp[i, j - 1], dp[i - 1, j]) + grid[i][j];
}
}
return dp[n - 1, m - 1];
}
/* 最小路徑和:動態規劃 */
func minPathSumDP(grid [][]int) int {
n, m := len(grid), len(grid[0])
// 初始化 dp 表
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
dp[0][0] = grid[0][0]
// 狀態轉移:首行
for j := 1; j < m; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
// 狀態轉移:首列
for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
// 狀態轉移:其餘行和列
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
dp[i][j] = int(math.Min(float64(dp[i][j-1]), float64(dp[i-1][j]))) + grid[i][j]
}
}
return dp[n-1][m-1]
}
/* 最小路徑和:動態規劃 */
func minPathSumDP(grid: [[Int]]) -> Int {
let n = grid.count
let m = grid[0].count
// 初始化 dp 表
var dp = Array(repeating: Array(repeating: 0, count: m), count: n)
dp[0][0] = grid[0][0]
// 狀態轉移:首行
for j in 1 ..< m {
dp[0][j] = dp[0][j - 1] + grid[0][j]
}
// 狀態轉移:首列
for i in 1 ..< n {
dp[i][0] = dp[i - 1][0] + grid[i][0]
}
// 狀態轉移:其餘行和列
for i in 1 ..< n {
for j in 1 ..< m {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
}
}
return dp[n - 1][m - 1]
}
/* 最小路徑和:動態規劃 */
function minPathSumDP(grid) {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = Array.from({ length: n }, () =>
Array.from({ length: m }, () => 0)
);
dp[0][0] = grid[0][0];
// 狀態轉移:首行
for (let j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 狀態轉移:首列
for (let i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 狀態轉移:其餘行和列
for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路徑和:動態規劃 */
function minPathSumDP(grid: Array<Array<number>>): number {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = Array.from({ length: n }, () =>
Array.from({ length: m }, () => 0)
);
dp[0][0] = grid[0][0];
// 狀態轉移:首行
for (let j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 狀態轉移:首列
for (let i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 狀態轉移:其餘行和列
for (let i = 1; i < n; i++) {
for (let j: number = 1; j < m; j++) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路徑和:動態規劃 */
int minPathSumDP(List<List<int>> grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
List<List<int>> dp = List.generate(n, (i) => List.filled(m, 0));
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];
}
/* 最小路徑和:動態規劃 */
fn min_path_sum_dp(grid: &Vec<Vec<i32>>) -> i32 {
let (n, m) = (grid.len(), grid[0].len());
// 初始化 dp 表
let mut dp = vec![vec![0; m]; n];
dp[0][0] = grid[0][0];
// 狀態轉移:首行
for j in 1..m {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 狀態轉移:首列
for i in 1..n {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 狀態轉移:其餘行和列
for i in 1..n {
for j in 1..m {
dp[i][j] = std::cmp::min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
dp[n - 1][m - 1]
}
/* 最小路徑和:動態規劃 */
int minPathSumDP(int grid[MAX_SIZE][MAX_SIZE], int n, int m) {
// 初始化 dp 表
int **dp = malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
dp[i] = calloc(m, sizeof(int));
}
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] = myMin(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
int res = dp[n - 1][m - 1];
// 釋放記憶體
for (int i = 0; i < n; i++) {
free(dp[i]);
}
return res;
}
/* 最小路徑和:動態規劃 */
fun minPathSumDP(grid: Array<IntArray>): Int {
val n = grid.size
val m = grid[0].size
// 初始化 dp 表
val dp = Array(n) { IntArray(m) }
dp[0][0] = grid[0][0]
// 狀態轉移:首行
for (j in 1..<m) {
dp[0][j] = dp[0][j - 1] + grid[0][j]
}
// 狀態轉移:首列
for (i in 1..<n) {
dp[i][0] = dp[i - 1][0] + grid[i][0]
}
// 狀態轉移:其餘行和列
for (i in 1..<n) {
for (j in 1..<m) {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
}
}
return dp[n - 1][m - 1]
}
### 最小路徑和:動態規劃 ###
def min_path_sum_dp(grid)
n, m = grid.length, grid.first.length
# 初始化 dp 表
dp = Array.new(n) { Array.new(m, 0) }
dp[0][0] = grid[0][0]
# 狀態轉移:首行
(1...m).each { |j| dp[0][j] = dp[0][j - 1] + grid[0][j] }
# 狀態轉移:首列
(1...n).each { |i| dp[i][0] = dp[i - 1][0] + grid[i][0] }
# 狀態轉移:其餘行和列
for i in 1...n
for j in 1...m
dp[i][j] = [dp[i][j - 1], dp[i - 1][j]].min + grid[i][j]
end
end
dp[n -1][m -1]
end
視覺化執行
圖 14-16 展示了最小路徑和的狀態轉移過程,其走訪了整個網格,因此時間複雜度為 \(O(nm)\) 。
陣列 dp 大小為 \(n \times m\) ,因此空間複雜度為 \(O(nm)\) 。
圖 14-16 最小路徑和的動態規劃過程
圖解 14-16:最小路徑和動態規劃
從左上角起點出發,先累計首行與首列的唯一邊界路徑,再按行逐格取上方與左方較小值加當前格代價,遞推至右下角終點。
給定 4×4 非負整數代價網格 grid(行列索引均從 0 開始,完整數值見輸入表),要求從左上角起點 [0,0] 走到右下角終點 [3,3],每步只能向右或向下移動一格,路徑總代價包含起點與終點的格值。
狀態表 dp[i,j] 表示從起點 [0,0] 到達第 i 行第 j 列格子的最小路徑和。建表之初填入的 0 僅表示尚未計算的初始佔位值,絕不代表存在一條代價為 0 的路徑。
邊界初始化:起點記為 dp[0,0] = grid[0,0] = 1;第 0 行只能從左方一路向右到達,第 0 列只能從上方一路向下到達,因此先沿首行、首列累加得到共 7 個有效邊界格。
內部遞推:對第 1 至 3 行、第 1 至 3 列的 9 個內部格,按行從左到右依次計算狀態轉移方程 dp[i,j] = min(dp[i-1,j], dp[i,j-1]) + grid[i,j],保證每次求值時上方 dp[i-1,j] 與左方 dp[i,j-1] 均已算出有效結果。每幀附帶的狀態表將格值與“未計算初值”“邊界有效”或“已計算”同時寫入單元格,便於按座標直接查閱。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
初始化dp儲存
建立 4×4 的 dp 狀態表並全部填入未計算初值 0;此時包括起點 [0,0]、第 0 行與第 0 列在內的全部 16 格均尚未求值,0 不代表零代價路徑。
最小路徑和第 1 步:初始化dp儲存後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 1 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 2 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 3 0,未計算初值 0,未計算初值 0,未計算初值 0,未計算初值 計算首行與首列邊界
起點 dp[0,0] = grid[0,0] = 1;第 0 行沿唯一向右路徑累加得到 [1, 4, 5, 10],第 0 列沿唯一向下路徑累加得到 [1, 3, 8, 12]。至此共 7 個邊界格成為有效邊界值,其餘 9 個內部格(行 1 至 3、列 1 至 3)仍為未計算初值 0。
最小路徑和第 2 步:計算首行與首列邊界後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 2 8,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 3 12,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 計算dp[1,1]
進入內部第 1 行第 1 列:上方前驅 dp[0,1]=4,左方前驅 dp[1,0]=3,取較小值 3 並加上當前格代價 grid[1,1]=2,算得 dp[1,1] = min(4, 3) + 2 = 5。其餘 8 個內部格([1,2]、[1,3] 以及行 2 至 3、列 1 至 3)仍為未計算初值 0。
最小路徑和第 3 步:計算dp[1,1]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 0,未計算初值 0,未計算初值 2 8,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 3 12,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 計算dp[1,2]
到達 [1,2]:上方前驅 dp[0,2]=5,左方前驅 dp[1,1]=5,兩處前驅值相等,任取其一加上當前格代價 grid[1,2]=4,算得 dp[1,2] = min(5, 5) + 4 = 9。其餘 7 個內部格([1,3] 以及行 2 至 3、列 1 至 3)仍為未計算初值 0。
最小路徑和第 4 步:計算dp[1,2]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 0,未計算初值 2 8,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 3 12,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 計算dp[1,3]
到達第 1 行末格 [1,3]:上方前驅 dp[0,3]=10,左方前驅 dp[1,2]=9,取較小值 9 加上當前格代價 grid[1,3]=2,算得 dp[1,3] = min(10, 9) + 2 = 11。第 1 行已全部有效;行 2 至 3、列 1 至 3 的 6 個內部格仍為未計算初值 0。
最小路徑和第 5 步:計算dp[1,3]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 3 12,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 計算dp[2,1]
推進到第 2 行首個內部格 [2,1]:上方前驅 dp[1,1]=5,左方前驅 dp[2,0]=8,取較小值 5 加上當前格代價 grid[2,1]=3,算得 dp[2,1] = min(5, 8) + 3 = 8。剩餘 5 個內部格([2,2]、[2,3] 以及第 3 行的列 1 至 3)仍為未計算初值 0。
最小路徑和第 6 步:計算dp[2,1]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 8,已計算 0,未計算初值 0,未計算初值 3 12,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 計算dp[2,2]
到達 [2,2]:上方前驅 dp[1,2]=9,左方前驅 dp[2,1]=8,取較小值 8 加上當前格代價 grid[2,2]=2,算得 dp[2,2] = min(9, 8) + 2 = 10。剩餘 4 個內部格([2,3]、[3,1]、[3,2]、[3,3])仍為未計算初值 0。
最小路徑和第 7 步:計算dp[2,2]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 8,已計算 10,已計算 0,未計算初值 3 12,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 計算dp[2,3]
到達第 2 行末格 [2,3]:上方前驅 dp[1,3]=11,左方前驅 dp[2,2]=10,取較小值 10 加上當前格代價 grid[2,3]=1,算得 dp[2,3] = min(11, 10) + 1 = 11。第 2 行已全部有效;僅剩第 3 行的 [3,1]、[3,2]、[3,3] 為未計算初值 0。
最小路徑和第 8 步:計算dp[2,3]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 8,已計算 10,已計算 11,已計算 3 12,邊界有效 0,未計算初值 0,未計算初值 0,未計算初值 計算dp[3,1]
推進到最後一行內部格 [3,1]:上方前驅 dp[2,1]=8,左方前驅 dp[3,0]=12,取較小值 8 加上當前格代價 grid[3,1]=3,算得 dp[3,1] = min(8, 12) + 3 = 11。僅剩 [3,2] 和終點 [3,3] 為未計算初值 0。
最小路徑和第 9 步:計算dp[3,1]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 8,已計算 10,已計算 11,已計算 3 12,邊界有效 11,已計算 0,未計算初值 0,未計算初值 計算dp[3,2]
到達 [3,2]:上方前驅 dp[2,2]=10,左方前驅 dp[3,1]=11,取較小值 10 加上當前格代價 grid[3,2]=5,算得 dp[3,2] = min(10, 11) + 5 = 15。其餘 15 格均已有效,僅剩終點 dp[3,3] 為 0(未計算初值)。
最小路徑和第 10 步:計算dp[3,2]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 8,已計算 10,已計算 11,已計算 3 12,邊界有效 11,已計算 15,已計算 0,未計算初值 計算dp[3,3]
計算最後一個內部格(終點)[3,3]:上方前驅為 dp[2,3]=11,左方前驅為 dp[3,2]=15,取較小值 11 加上當前格代價 grid[3,3]=2,算得 dp[3,3] = min(11, 15) + 2 = 13。至此全表 16 格均已有效。
最小路徑和第 11 步:計算dp[3,3]後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 8,已計算 10,已計算 11,已計算 3 12,邊界有效 11,已計算 15,已計算 13,已計算 返回最小路徑和
全部 16 個狀態格已計算完畢,本步不再執行新計算,直接讀取並返回右下角終點狀態 dp[3,3] = 13 作為最小路徑和。本過程只返回最小累計代價,未回溯輸出具體路徑座標。
最小路徑和第 12 步:返回最小路徑和後的 dp 狀態 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,邊界有效 4,邊界有效 5,邊界有效 10,邊界有效 1 3,邊界有效 5,已計算 9,已計算 11,已計算 2 8,邊界有效 8,已計算 10,已計算 11,已計算 3 12,邊界有效 11,已計算 15,已計算 13,已計算
4. 空間最佳化¶
由於每個格子只與其左邊和上邊的格子有關,因此我們可以只用一個單行陣列來實現 \(dp\) 表。
請注意,因為陣列 dp 只能表示一行的狀態,所以我們無法提前初始化首列狀態,而是在走訪每行時更新它:
def min_path_sum_dp_comp(grid: list[list[int]]) -> int:
"""最小路徑和:空間最佳化後的動態規劃"""
n, m = len(grid), len(grid[0])
# 初始化 dp 表
dp = [0] * m
# 狀態轉移:首行
dp[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]
/* 最小路徑和:空間最佳化後的動態規劃 */
int minPathSumDPComp(vector<vector<int>> &grid) {
int n = grid.size(), m = grid[0].size();
// 初始化 dp 表
vector<int> dp(m);
// 狀態轉移:首行
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[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];
}
/* 最小路徑和:空間最佳化後的動態規劃 */
int minPathSumDPComp(int[][] grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
int[] dp = new int[m];
// 狀態轉移:首行
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[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] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路徑和:空間最佳化後的動態規劃 */
int MinPathSumDPComp(int[][] grid) {
int n = grid.Length, m = grid[0].Length;
// 初始化 dp 表
int[] dp = new int[m];
dp[0] = grid[0][0];
// 狀態轉移:首行
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[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] = Math.Min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路徑和:空間最佳化後的動態規劃 */
func minPathSumDPComp(grid [][]int) int {
n, m := len(grid), len(grid[0])
// 初始化 dp 表
dp := make([]int, m)
// 狀態轉移:首行
dp[0] = grid[0][0]
for j := 1; j < m; j++ {
dp[j] = dp[j-1] + grid[0][j]
}
// 狀態轉移:其餘行和列
for i := 1; i < n; i++ {
// 狀態轉移:首列
dp[0] = dp[0] + grid[i][0]
// 狀態轉移:其餘列
for j := 1; j < m; j++ {
dp[j] = int(math.Min(float64(dp[j-1]), float64(dp[j]))) + grid[i][j]
}
}
return dp[m-1]
}
/* 最小路徑和:空間最佳化後的動態規劃 */
func minPathSumDPComp(grid: [[Int]]) -> Int {
let n = grid.count
let m = grid[0].count
// 初始化 dp 表
var dp = Array(repeating: 0, count: m)
// 狀態轉移:首行
dp[0] = grid[0][0]
for j in 1 ..< m {
dp[j] = dp[j - 1] + grid[0][j]
}
// 狀態轉移:其餘行
for i in 1 ..< n {
// 狀態轉移:首列
dp[0] = dp[0] + grid[i][0]
// 狀態轉移:其餘列
for j in 1 ..< m {
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
}
}
return dp[m - 1]
}
/* 最小路徑和:空間最佳化後的動態規劃 */
function minPathSumDPComp(grid) {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = new Array(m);
// 狀態轉移:首行
dp[0] = grid[0][0];
for (let j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 狀態轉移:其餘行
for (let i = 1; i < n; i++) {
// 狀態轉移:首列
dp[0] = dp[0] + grid[i][0];
// 狀態轉移:其餘列
for (let j = 1; j < m; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路徑和:空間最佳化後的動態規劃 */
function minPathSumDPComp(grid: Array<Array<number>>): number {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = new Array(m);
// 狀態轉移:首行
dp[0] = grid[0][0];
for (let j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 狀態轉移:其餘行
for (let i = 1; i < n; i++) {
// 狀態轉移:首列
dp[0] = dp[0] + grid[i][0];
// 狀態轉移:其餘列
for (let j = 1; j < m; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路徑和:空間最佳化後的動態規劃 */
int minPathSumDPComp(List<List<int>> grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
List<int> dp = List.filled(m, 0);
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[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];
}
/* 最小路徑和:空間最佳化後的動態規劃 */
fn min_path_sum_dp_comp(grid: &Vec<Vec<i32>>) -> i32 {
let (n, m) = (grid.len(), grid[0].len());
// 初始化 dp 表
let mut dp = vec![0; m];
// 狀態轉移:首行
dp[0] = grid[0][0];
for j in 1..m {
dp[j] = dp[j - 1] + grid[0][j];
}
// 狀態轉移:其餘行
for i in 1..n {
// 狀態轉移:首列
dp[0] = dp[0] + grid[i][0];
// 狀態轉移:其餘列
for j in 1..m {
dp[j] = std::cmp::min(dp[j - 1], dp[j]) + grid[i][j];
}
}
dp[m - 1]
}
/* 最小路徑和:空間最佳化後的動態規劃 */
int minPathSumDPComp(int grid[MAX_SIZE][MAX_SIZE], int n, int m) {
// 初始化 dp 表
int *dp = calloc(m, sizeof(int));
// 狀態轉移:首行
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[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] = myMin(dp[j - 1], dp[j]) + grid[i][j];
}
}
int res = dp[m - 1];
// 釋放記憶體
free(dp);
return res;
}
/* 最小路徑和:空間最佳化後的動態規劃 */
fun minPathSumDPComp(grid: Array<IntArray>): Int {
val n = grid.size
val m = grid[0].size
// 初始化 dp 表
val dp = IntArray(m)
// 狀態轉移:首行
dp[0] = grid[0][0]
for (j in 1..<m) {
dp[j] = dp[j - 1] + grid[0][j]
}
// 狀態轉移:其餘行
for (i in 1..<n) {
// 狀態轉移:首列
dp[0] = dp[0] + grid[i][0]
// 狀態轉移:其餘列
for (j in 1..<m) {
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
}
}
return dp[m - 1]
}
### 最小路徑和:空間最佳化後的動態規劃 ###
def min_path_sum_dp_comp(grid)
n, m = grid.length, grid.first.length
# 初始化 dp 表
dp = Array.new(m, 0)
# 狀態轉移:首行
dp[0] = grid[0][0]
(1...m).each { |j| dp[j] = dp[j - 1] + grid[0][j] }
# 狀態轉移:其餘行
for i in 1...n
# 狀態轉移:首列
dp[0] = dp[0] + grid[i][0]
# 狀態轉移:其餘列
(1...m).each { |j| dp[j] = [dp[j - 1], dp[j]].min + grid[i][j] }
end
dp[m - 1]
end