发表于 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];
      }
  };

• LC 题目链接