NC59.矩阵的最小路径和

题目描述 (opens new window)

解题思路

此题是典型的动态规划的题目。

• 状态定义：

  • 设dp为大小 m x n 矩阵，其中dp[i][j]的值代表直到走到(i,j)的最小路径和。

• 转移方程:

题目要求，只能向右或者向下走，换句话说，当前单元格（i，j）只能从左方单元格 （i-1,j）或者上方单元格（i，j-1）走到，因此只需要考虑矩阵左边界和上边界。

走到当前单元格（i，j）的最小路径和 = "从左方单元格（i-1, j）"与从上方单元格（i，j-1）走来的两个最小路径中较小的” + 当前单元格值[i][j] 具体分为以下四种情况。

1、 当左边和上边都不是矩阵的边界时：即当 i!==0 j!==0 dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j] 2、 只有左边界是矩阵的边界时候；只能从上面来，即当 i = 0 j !=0 时候，dp[i][j] = dp[i][j-1] + grid[i][j] 3、 当只有上边界是矩阵的边界时：只能从左边来，即当 i !=0 j = 0 时候，dp[i][j] = dp[i-1][j] + grid[i][j] 4、 当左边界和上边界都是矩阵的边界时: 即当 i = 0, j=0 其实就是起点 dp[i][j] = grid[i][j]

• 初始状态

  • dp初始化即可，不需要修改初始0值

• 返回值

  • 返回dp矩阵右下角的值，即走到终点的最小路径和

其实我们完全不需要建立dp矩阵浪费额外空间，直接遍历grid[i][j]修改即可，这是因为：grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]; 原 grid 矩阵元素中被覆盖为 dp 元素后（都处于当前遍历点的左上方），不会再被使用到。

/**
 * @param {number[][]} grid
 * @return {number}
 */

var minPathSum = function (grid) {
  // 外层的循环是行级别的
  for (let i = 0; i < grid.length; i++) {
    // 内层循环的是列
    for (let j = 0; j < grid[0].length; j++) {
      if (i === 0 && j === 0) { // 这就是第一个 
        continue
      } else if (i === 0) {  // 边界在上面，只能向右移动
        grid[i][j] = grid[i][j - 1] + grid[i][j];
      } else if (j === 0) { // 边界在左边 只能向下移动
        grid[i][j] = grid[i - 1][j] + grid[i][j];
      } else { // 不再上边界和左边界的点
        grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
      }
    }
  }
  return grid[grid.length - 1][grid[0].length - 1]
};