跳轉至

14.3   動態規劃解題思路

上兩節介紹了動態規劃問題的主要特徵,接下來我們一起探究兩個更加實用的問題。

  1. 如何判斷一個問題是不是動態規劃問題?
  2. 求解動態規劃問題該從何處入手,完整步驟是什麼?

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”。

最優路徑示例:輸入網格 grid(行列索引從 0 開始)
行索引列 0列 1列 2列 3
01315
12242
25321
34352

右側綠色最優路徑從起點 [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],分別對應到達各格的最小路徑和子問題。本圖只建立狀態定義與座標對映,尚未計算和填寫具體路徑和數值。

狀態定義:輸入網格 grid(行列索引從 0 開始)
行索引列 0列 1列 2列 3
01315
12242
25321
34352

圖底部依次列出四項建模定義:決策是每輪向右或向下走一格;狀態是所在格子的行列索引 [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 所示的狀態轉移方程:

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

圖 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。

狀態轉移:輸入網格 grid(行列索引從 0 開始)
行索引列 0列 1列 2列 3
01315
12242
25321
34352

以圖中綠色高亮的內部格 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] 已在本行左側算好。下表的計算公式據圖中的邊界和前驅關係整理,原圖沒有逐項寫出這些公式。

4×4 符號表的初始化與內部遞推
區域索引範圍前驅計算方式
起點[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\) ,代表不可行。

實現程式碼如下:

min_path_sum.py
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]
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 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;
}
min_path_sum.java
/* 最小路徑和:暴力搜尋 */
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];
}
min_path_sum.cs
/* 最小路徑和:暴力搜尋 */
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];
}
min_path_sum.go
/* 最小路徑和:暴力搜尋 */
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]
}
min_path_sum.swift
/* 最小路徑和:暴力搜尋 */
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]
}
min_path_sum.js
/* 最小路徑和:暴力搜尋 */
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];
}
min_path_sum.ts
/* 最小路徑和:暴力搜尋 */
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];
}
min_path_sum.dart
/* 最小路徑和:暴力搜尋 */
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];
}
min_path_sum.rs
/* 最小路徑和:暴力搜尋 */
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]
}
min_path_sum.c
/* 最小路徑和:暴力搜尋 */
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;
}
min_path_sum.kt
/* 最小路徑和:暴力搜尋 */
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]
}
min_path_sum.rb
### 最小路徑和:暴力搜尋 ###
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 ,用於記錄各個子問題的解,並將重疊子問題進行剪枝:

min_path_sum.py
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]
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 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];
}
min_path_sum.java
/* 最小路徑和:記憶化搜尋 */
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];
}
min_path_sum.cs
/* 最小路徑和:記憶化搜尋 */
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];
}
min_path_sum.go
/* 最小路徑和:記憶化搜尋 */
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]
}
min_path_sum.swift
/* 最小路徑和:記憶化搜尋 */
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]
}
min_path_sum.js
/* 最小路徑和:記憶化搜尋 */
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];
}
min_path_sum.ts
/* 最小路徑和:記憶化搜尋 */
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];
}
min_path_sum.dart
/* 最小路徑和:記憶化搜尋 */
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];
}
min_path_sum.rs
/* 最小路徑和:記憶化搜尋 */
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]
}
min_path_sum.c
/* 最小路徑和:記憶化搜尋 */
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];
}
min_path_sum.kt
/* 最小路徑和:記憶化搜尋 */
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]
}
min_path_sum.rb
### 最小路徑和:記憶化搜尋 ###
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.   方法三:動態規劃

基於迭代實現動態規劃解法,程式碼如下所示:

min_path_sum.py
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]
min_path_sum.cpp
/* 最小路徑和:動態規劃 */
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];
}
min_path_sum.java
/* 最小路徑和:動態規劃 */
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];
}
min_path_sum.cs
/* 最小路徑和:動態規劃 */
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];
}
min_path_sum.go
/* 最小路徑和:動態規劃 */
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]
}
min_path_sum.swift
/* 最小路徑和:動態規劃 */
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]
}
min_path_sum.js
/* 最小路徑和:動態規劃 */
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];
}
min_path_sum.ts
/* 最小路徑和:動態規劃 */
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];
}
min_path_sum.dart
/* 最小路徑和:動態規劃 */
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];
}
min_path_sum.rs
/* 最小路徑和:動態規劃 */
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]
}
min_path_sum.c
/* 最小路徑和:動態規劃 */
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;
}
min_path_sum.kt
/* 最小路徑和:動態規劃 */
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]
}
min_path_sum.rb
### 最小路徑和:動態規劃 ###
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] 均已算出有效結果。每幀附帶的狀態表將格值與“未計算初值”“邊界有效”或“已計算”同時寫入單元格,便於按座標直接查閱。

動態規劃過程:輸入網格 grid(行列索引從 0 開始)
行索引列 0列 1列 2列 3
01315
12242
25321
34352
  1. 初始化dp儲存

    建立 4×4 的 dp 狀態表並全部填入未計算初值 0;此時包括起點 [0,0]、第 0 行與第 0 列在內的全部 16 格均尚未求值,0 不代表零代價路徑。

    最小路徑和第 1 步:初始化dp儲存後的 dp 狀態
    行索引i列j=0列j=1列j=2列j=3
    00,未計算初值0,未計算初值0,未計算初值0,未計算初值
    10,未計算初值0,未計算初值0,未計算初值0,未計算初值
    20,未計算初值0,未計算初值0,未計算初值0,未計算初值
    30,未計算初值0,未計算初值0,未計算初值0,未計算初值
  2. 計算首行與首列邊界

    起點 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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效0,未計算初值0,未計算初值0,未計算初值
    28,邊界有效0,未計算初值0,未計算初值0,未計算初值
    312,邊界有效0,未計算初值0,未計算初值0,未計算初值
  3. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算0,未計算初值0,未計算初值
    28,邊界有效0,未計算初值0,未計算初值0,未計算初值
    312,邊界有效0,未計算初值0,未計算初值0,未計算初值
  4. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算0,未計算初值
    28,邊界有效0,未計算初值0,未計算初值0,未計算初值
    312,邊界有效0,未計算初值0,未計算初值0,未計算初值
  5. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效0,未計算初值0,未計算初值0,未計算初值
    312,邊界有效0,未計算初值0,未計算初值0,未計算初值
  6. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效8,已計算0,未計算初值0,未計算初值
    312,邊界有效0,未計算初值0,未計算初值0,未計算初值
  7. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效8,已計算10,已計算0,未計算初值
    312,邊界有效0,未計算初值0,未計算初值0,未計算初值
  8. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效8,已計算10,已計算11,已計算
    312,邊界有效0,未計算初值0,未計算初值0,未計算初值
  9. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效8,已計算10,已計算11,已計算
    312,邊界有效11,已計算0,未計算初值0,未計算初值
  10. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效8,已計算10,已計算11,已計算
    312,邊界有效11,已計算15,已計算0,未計算初值
  11. 計算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
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效8,已計算10,已計算11,已計算
    312,邊界有效11,已計算15,已計算13,已計算
  12. 返回最小路徑和

    全部 16 個狀態格已計算完畢,本步不再執行新計算,直接讀取並返回右下角終點狀態 dp[3,3] = 13 作為最小路徑和。本過程只返回最小累計代價,未回溯輸出具體路徑座標。

    最小路徑和第 12 步:返回最小路徑和後的 dp 狀態
    行索引i列j=0列j=1列j=2列j=3
    01,邊界有效4,邊界有效5,邊界有效10,邊界有效
    13,邊界有效5,已計算9,已計算11,已計算
    28,邊界有效8,已計算10,已計算11,已計算
    312,邊界有效11,已計算15,已計算13,已計算

4.   空間最佳化

由於每個格子只與其左邊和上邊的格子有關,因此我們可以只用一個單行陣列來實現 \(dp\) 表。

請注意,因為陣列 dp 只能表示一行的狀態,所以我們無法提前初始化首列狀態,而是在走訪每行時更新它:

min_path_sum.py
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]
min_path_sum.cpp
/* 最小路徑和:空間最佳化後的動態規劃 */
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];
}
min_path_sum.java
/* 最小路徑和:空間最佳化後的動態規劃 */
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];
}
min_path_sum.cs
/* 最小路徑和:空間最佳化後的動態規劃 */
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];
}
min_path_sum.go
/* 最小路徑和:空間最佳化後的動態規劃 */
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]
}
min_path_sum.swift
/* 最小路徑和:空間最佳化後的動態規劃 */
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]
}
min_path_sum.js
/* 最小路徑和:空間最佳化後的動態規劃 */
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];
}
min_path_sum.ts
/* 最小路徑和:空間最佳化後的動態規劃 */
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];
}
min_path_sum.dart
/* 最小路徑和:空間最佳化後的動態規劃 */
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];
}
min_path_sum.rs
/* 最小路徑和:空間最佳化後的動態規劃 */
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]
}
min_path_sum.c
/* 最小路徑和:空間最佳化後的動態規劃 */
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;
}
min_path_sum.kt
/* 最小路徑和:空間最佳化後的動態規劃 */
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]
}
min_path_sum.rb
### 最小路徑和:空間最佳化後的動態規劃 ###
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
視覺化執行

歡迎在評論區留下你的見解、問題或建議