64. 最小路径和

难度：🟡 Medium | 标签：动归 | 状态：⬜ LeetCode 链接

思路

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。 原地改 grid 省空间。

代码

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

复杂度

• 时间 O(R · C)，空间 O(1)（原地）

易错 / 回顾

• 首行 / 首列只能从一个方向来
• 原地修改要小心 (0,0) 不要重算
• 若不能改原数组，开 O(C) 滚动数组