LeetCode.64 - 最小路径和

• LeetCode - 64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

思路

1. 动态规划，dp[m + 1][n + 1] = Math.min(dp[m][n + 1], dp[m + 1][n]) + grid[i][j]
2. 由于是按行顺序遍历，可以使用一维数组代替二维数组以节省内存开销

var minPathSum = function (grid) {
  const [M, N] = [grid.length, grid[0].length]
  let curSums = [...grid[0]]
  for (let j = 1; j < curSums.length; ++j) {
    curSums[j] += curSums[j - 1]
  }
  for (let i = 1; i < M; ++i) {
    curSums[0] = curSums[0] + grid[i][0]
    for (let j = 1; j < N; ++j) {
      curSums[j] = Math.min(curSums[j], curSums[j - 1]) + grid[i][j]
    }
  }
  return curSums[N - 1]
}