题目:
难度:Middle
相关话题:数组
、动态规划
给定一个包含非负整数的 m xn 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明: 每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思路:
与NO.62
和NO.63
一个模式。
dp[i][j]
代表当前位置的最小路径和,状态转移方程:
右侧:dp[i+1][j]=Math.min(dp[i+1][j],dp[i][j]+grid[i+1][j])
下侧:dp[i][j+1]=Math.min(dp[i][j+1],dp[i][j]+grid[i][j+1])
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
if(grid.length===0)return 0
let m=grid.length,n=grid[0].length
let dp=Array(m).fill().map(()=>Array(n).fill(Infinity))
dp[0][0]=grid[0][0]
for(let i=0;i<m;i++){
for(let j=0;j<n;j++){
if(i<m-1){
dp[i+1][j]=Math.min(dp[i+1][j],dp[i][j]+grid[i+1][j])
}
if(j<n-1){
dp[i][j+1]=Math.min(dp[i][j+1],dp[i][j]+grid[i][j+1])
}
}
}
return dp[m-1][n-1]
};