专栏首页freesan44LeetCode 64. 最小路径和

LeetCode 64. 最小路径和

题目

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

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

示例:

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

解题思路

    def minPathSum(self, grid: [[int]]) -> int:
        rowLen = len(grid[0])
        colLen = len(grid)
        countGrid = [[0]*rowLen for i in range(colLen)]#初始化统计步数矩阵
        countGrid[0][0] = grid[0][0]
        for i in range(1, rowLen):
            countGrid[0][i] = countGrid[0][i-1] + grid[0][i]
        for j in range(1, colLen):
            countGrid[j][0] = countGrid[j-1][0] + grid[j][0]
        # print(countGrid)
        for i in range(1, rowLen):##每个步数元素,存储从左边和上边的最小值,再加上自身的值,为自己所在元素的最小步数
            for j in range(1, colLen):
                # print("{} {}".format(j, i))
                countGrid[j][i] = min(countGrid[j][i-1], countGrid[j-1][i]) + grid[j][i]

        return countGrid[colLen-1][rowLen-1]

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 62. 不同路径

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    freesan44
  • Python for Everything

    freesan44
  • LeetCode 20. 有效的括号

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    freesan44
  • sql返回指定节点的树形结构数据

    请叫我树形图 使用sql,返回部门1以及其子部门数据。 很明显就是一个树形递归嘛,用代码就比较好实现。 但是要用sql实现,就稍微麻烦点。...

    用户5166330
  • 【OCP最新题库解析(052)--题49】Examine these facts about a database.

    该系列专题为2018年4月OCP-052考题变革后的最新题库。题库为小麦苗解答,若解答有不对之处,可留言,也可联系小麦苗进行修改。

    小麦苗DBA宝典
  • 200 道算法面试题集锦!Python 实现,含华为、BAT 等校招真题!

    春招临近,无论是要找工作的准毕业生,还是身在职场想要提升自己的程序员,提升自己的算法内功心法、提升 Python 编程能力,总是大有裨益的。今天,红色石头发现了...

    用户2769421
  • Linux+Nginx/Apache/Tomcat新增SSL证书,开启https访问教程

    上上篇文章《nginx 平滑升级&新增模块》提到了公司的 https 访问需求。当我新增了 SSL 模块之后,却发现以前还真没部署过 https 访问。 下面整...

    张戈
  • Powershell 美化和 Win 包管理工具

    PowerShell 安装 Chocolatey 非常简单,管理员运行,然后输入如下指令

    李郑
  • 自然语言处理 | 使用Spacy 进行自然语言处理(二)

    上次我们简单介绍了Spacy,学习了它的安装以及实体识别等基本的方法。今天我继续给大家介绍一下它的其他功能如何操作,主要有词性还原,词性标注,名词块识别,依存分...

    用户1622570
  • 让网站用上https

    个人认为让一个没什么流量的网站支持https是没什么意义的,第一,支持https后访问速度会变慢 而且浪费服务器资源,但是没办法,一切为了装逼,为了装逼的一切...

    bboysoul

扫码关注云+社区

领取腾讯云代金券