064. 最小路径和

题目描述:

难度：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]
};