JZX轻语：简
LeetCode LCR 099 - 最小路径和
发表于2025年02月22日
经典动态规划题，就地使用grid数组记录到达每个位置的最小路径和，最后返回grid[m - 1][n - 1]即可。状态转移方程为：
如果
r == 0 && c == 0（起始点），则grid[r][c]不变；如果
r == 0 && c != 0（第一行），则grid[r][c]加上grid[r][c - 1]；如果
r != 0 && c == 0（第一列），则grid[r][c]加上grid[r - 1][c]；否则，
grid[r][c]加上min(grid[r - 1][c], grid[r][c - 1])。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
auto m = grid.size(), n = grid[0].size();
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (r == 0 && c == 0) continue;
else if (r == 0 /** && c != 0 **/) grid[r][c] += grid[r][c - 1];
else if (c == 0 /** && r != 0 **/) grid[r][c] += grid[r - 1][c];
else grid[r][c] += min(grid[r - 1][c], grid[r][c - 1]);
}
}
return grid[m - 1][n - 1];
}
};