给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
示例2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
每次只能向右或者向下移动一个位置,那就从[0, 0]开始,每次向右或者向下移动,取两者中数字较小的移动。一直移动到目标位置,
其中第一行的元素只能由向右移动得到,
第一列的元素只能由向下移动得到。
为了节省空间,就在 grid 上修改内容,不再重新声明数组。
var minPathSum = function(grid) {
// m: grid的行数,n: grid 的列数
let m = grid.length,
n = grid[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; 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[m-1][n-1]
};