您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 64 最小路徑和：二維 DP 空間優化至一維完整攻略

編輯：關於C++

問題描述

m×n 非負整數矩陣，從左上角走到右下角，只能向右或向下，求路徑上數字和的最小值。

二維 DP 基礎版


int minPathSum(vector>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector> dp(m+1, vector(n+1, INT_MAX));
    dp[0][1] = 0; // 虛擬起點
    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]) + grid[i-1][j-1];
    return dp[m][n];
}

一維 DP 空間優化（按列掃描）

觀察：dp[i][j] 只依賴 dp[i-1][j]（上，即舊 cur[i]）和 dp[i][j-1]（左，即新 cur[i-1]）。
用一維數組 cur[m] 表示當前列的最小和。


int minPathSum(vector>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector cur(m, grid[0][0]);
    for (int i = 1; i < m; ++i) cur[i] = cur[i-1] + grid[i][0]; // 初始化第一列
    for (int j = 1; j < n; ++j) {
        cur[0] += grid[0][j]; // 第一行只能從左來
        for (int i = 1; i < m; ++i)
            cur[i] = min(cur[i-1], cur[i]) + grid[i][j];
    }
    return cur[m-1];
}

按行掃描版本（對稱）


vector cur(n, grid[0][0]);
for (int j = 1; j < n; ++j) cur[j] = cur[j-1] + grid[0][j];
for (int i = 1; i < m; ++i) {
    cur[0] += grid[i][0];
    for (int j = 1; j < n; ++j)
        cur[j] = min(cur[j-1], cur[j]) + grid[i][j];
}
return cur[n-1];