1. 首页
  2. LeetCode 刷题网

064. 最小路径和

题目描述:

难度:Middle

相关话题:数组动态规划

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

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

示例:

输入:
[
 [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思路:

NO.62NO.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]
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「IT平头哥联盟」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:064. 最小路径和

链接:https://www.javascriptc.com/4424.html

« 如何Nginx实现负载均衡
063. 不同路径 II»
Flutter 中文教程资源

相关推荐

QR code