給定m乘n網(wǎng)格填充非負(fù)數(shù)辅甥，找到從左上到右下的路徑子姜，最小化沿其路徑的所有數(shù)字總和祟绊，只能在任何時(shí)間點(diǎn)向下或向右移動(dòng)
動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)
- Runtime: 72 ms, faster than 96.42%
- Memory Usage: 37.4 MB, less than 68.59%
首先確定第一行和第一列，后面逐行逐列得到哥捕。
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
let m = grid.length
let n = grid[0].length
for(let i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0]
}
for (let i = 1; i < n; i++) {
grid[0][i] += grid[0][i - 1]
}
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
}
}
return grid[m - 1][n - 1]
};
