专栏首页前端路桥leetcode - 最小路径和

leetcode - 最小路径和

题目描述

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

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

示例:

输入:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。

题解

起先,这题我是来了一波深度搜索,我是抓牢一个点就是从左顶点往下走或者是往右走,在这之后我只选择最小的那个点走,试了下测试用例也还OK,提交了以后没有通过,我陷入了深思,发现我的脑容量还是不够大,too young too simple, sometimes navie. 后来也想到了这种方法有点危险,及时悔悟啊。。。

排除掉m和n中有一个为0的情况,我们进行分类讨论。

  • 当m为0时,靠边上那一排单纯点往右边走,计算出每位选手的最小和
  • 当n为0时,靠边上那一列单纯点往下走,计算出每位选手的最小和
  • 排除楼上两种情况后,考虑中间任意点的最小和等于其自身加上和其自身相邻的左边那位或者上边那位的最小和的最小值

最后,我们只要返回最后那个元素的最小和就好了。

用Javascript语言的相关实现如下:

/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function (grid) {
 var row = grid.length;
 if (!row) return 0;
 var col = grid[row - 1].length;
 if (!col) return 0;
 var dp = [...grid];
 for (var i = 1; i < row; i++) {
   dp[i][0] = grid[i - 1][0] + grid[i][0];
}

 for (var i = 1; i < col; i++) {
   dp[0][i] = grid[0][i - 1] + grid[0][i];
}

 for(var i = 1; i < row; i++) {
   for (var j = 1; j < col; j++) {
     dp[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
  }
}

 return dp[row - 1][col - 1];
};

emmmm, 这里提及一下,在JS中数组是引用类型的,所以你要用深拷贝来解决数组拷贝问题。

代码地址: https://zhengjiangtao.cn/coding/interview/min_path_sum.js

项目地址: https://github.com/ataola/coding

参考文献

leetcode - 最小路径和:https://leetcode-cn.com/problems/minimum-path-sum

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Javascript[0x06] -- 基于Javascript范畴代码风格和规范的总结

    抓重点: 这么多要看到猴年马月去,找一个对的上眼的深入学习下,切勿都学,没这个必要,粗略扫读,有针对性阅读!

    丰臣正一
  • vue[0x01] -- Hello World

    如果你看过一千部以上的电影,你就会发现,这世间根本没有什么离奇的事。为什么从后端或者说网页三剑客过来的哥们,会有觉得vue上手快,容易学的错觉?很大程度上,在早...

    丰臣正一
  • FE[0x02] -- 浅谈CSS布局

    最开始网页有个p的布局,基本上打开大屁股头电脑能看文字就好了,再后来随着Web技术的发展,你可以选择浮动布局float,也可以结合position进行布局,还...

    丰臣正一
  • DFS&BFS - 200. Number of Islands

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

    用户5705150
  • JavaScript中的with关键字

    原文:http://luopq.com/2016/02/14/js-with-keyword/

    疯狂的技术宅
  • 删除所选项(附加搜索部分的jquery)

    wfaceboss
  • LeetCode 1267. 统计参与通信的服务器(计数)

    这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。

    Michael阿明
  • js去重方法

    windseek
  • 新能力| 云开发静态网站托管能力正式上线

    在互联网时代,网站建设不仅代替了传统的纸质彩页、海报宣传,更有利于企业形象及效率的提升,于是各行各业纷纷建起了属于自己的网站。

    云存储
  • 深度学习GPU卡性能比拼:见证Titan RTX“钞能力”

    文中,作者测试了包含Titan RTX在内的多个常见NVIDIA GPU卡在各种AI训练任务上的速度。对于每个GPU,分别训练下列神经网络时测量每秒处理的图像数...

    GPUS Lady

扫码关注云+社区

领取腾讯云代金券