1、思路

• grid[i][j]表示从坐标(0, 0)移动到坐标(i, j)路径上的最小数组和；

• 当前状态只能从上方或者左方转移过来，而且路径和还要加上当前状态本身，故状态转移方程为grid[i][j] += grid[i - 1][j] + grid[i][j - 1]；

• 初始化：第一行与第一列的路径只有一种，直接累加即可；

• 时间复杂度为 $O(nm)$，因为是在原地进行dp，故空间复杂度为 $O(1)$ 。

2、代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        for (int i = 1; i < n; ++ i) grid[i][0] += grid[i - 1][0];  //初始化
        for (int j = 1; j < m; ++ j) grid[0][j] += grid[0][j - 1];

        for (int i = 1; i < n; ++ i)
        {
            for (int j = 1; j < m; ++ j)
            {
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);  //状态转移方程
            }
        }

        return grid[n - 1][m - 1];
    }
};