dp[i][j] 表示从左上角开始到 (i, j) 位置的最 优路径的数字和

首先先不要考虑空间压缩

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (i == 0 && j == 0) continue;
                else if (i == 0) grid[i][j] += grid[i][j - 1];
                else if (j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[n - 1][m - 1];
    }
};

因为 dp 数组是按行从左到右遍历的，处理下一行时上一行的数据都已经处理完，所以可以直接在上一行上处理数据。也就说只需要只需要一行就可以了，二维数组可以压缩为一维数组。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> f(m);
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (i == 0 && j == 0) f[j] = grid[i][j];
                else if (!i) f[j] = grid[i][j] + f[j - 1];
                else if (!j) f[j] = grid[i][j] + f[j];
                else f[j] = grid[i][j] + min(f[j], f[j - 1]);
            }
        }
        return f[m - 1];
    }
};