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

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

思路

  1. 动态规划,dp[m + 1][n + 1] = Math.min(dp[m][n + 1], dp[m + 1][n]) + grid[i][j]
  2. 由于是按行顺序遍历,可以使用一维数组代替二维数组以节省内存开销
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]
}