矩陣最小路徑和 - 動態規劃經典模型

問題描述

給定 m×n 矩陣，每個格子非負整數。從左上角 (0,0) 走到右下角 (m-1,n-1)，每步只能向右或向下。求路徑上數字和的最小值。

動態規劃

狀態：dp[i][j] 從 (0,0) 走到 (i,j) 的最小路徑和。

初始化：dp[0][0] = a[0][0]。第一行只能從左來：dp[0][j] = dp[0][j-1] + a[0][j]。第一列只能從上來：dp[i][0] = dp[i-1][0] + a[i][0]。

轉移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j] (i,j > 0)。

答案：dp[m-1][n-1]。

代碼實現（C）

#include 
#include 

#define min(x,y) ((x)<(y)?(x):(y))

int minPathSum(int a[][5], int m, int n) {
    int dp[100][100];
    dp[0][0] = a[0][0];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + a[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + a[0][j];
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j];
    return dp[m-1][n-1];
}

int main() {
    int a[4][5] = {
        {1,1,1,1,1},
        {1,0,2,0,3},
        {0,1,2,1,0},
        {1,0,1,0,0}
    };
    printf("%d\n", minPathSum(a, 4, 5)); // 輸出最小和
    return 0;
}

空間優化

只需一維數組 dp[n] 滾動更新：dp[j] = min(dp[j], dp[j-1]) + a[i][j]。