【leetcode】最小路径和（动态规划）

柔光的暖阳◎ 2022-03-06 10:20 248阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

# 算法思想 #

不需要再使用函数了，直接初始化一个数组就行，使用一个二重循环。  
遍历一遍，如果i和j都是0，那么直接初始化，否则按照路径初始化

class Solution:
        def minPathSum(self, grid: List[List[int]]) -> int:
            if grid == []:
                return 0
            rows, cols = len(grid), len(grid[0])
            memory = [([0] * cols) for i in range(rows)]
            for i in range(rows):
                for j in range(cols):
                    if i - 1 >= 0 and j - 1 >= 0:
                        memory[i][j] = min(memory[i - 1][j], memory[i][j - 1]) + grid[i][j]
                    elif i - 1 >= 0:
                        memory[i][j] = memory[i - 1][j] + grid[i][j]
                    elif j - 1 >= 0:
                        memory[i][j] = memory[i][j - 1] + grid[i][j]
                    else:
                        memory[i][j] = grid[i][j]
            return memory[rows - 1][cols - 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220303/f58bae158e884ac4bff5dd3034da63d4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，248人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划之下降路径最小和

1. 题目分析题目链接选自力扣 : [下降路径最小和][Link 1] ![image.png][] 如果光看这个题目说明的话, 是有点抽象的. 我们结合实例

╰半夏微凉°/ 2024年03月16日 22:48/ 0 赞/ 111 阅读

相关动态规划之最小路径和

1. 题目分析题目链接选自力扣 : [最小路径和][Link 1] ![image.png][] 前面解触了很多路径题. 这依然是一个路径题, 题目要求从左上角

深碍√TFBOYSˉ_/ 2024年03月16日 22:48/ 0 赞/ 72 阅读

相关 LeetCode_动态规划_中等_120.三角形最小路径和

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到

港控/mmm°/ 2023年10月06日 23:25/ 0 赞/ 39 阅读

相关 LeetCode_动态规划_中等_64.最小路径和

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的

素颜马尾好姑娘i/ 2023年10月06日 19:01/ 0 赞/ 54 阅读

相关 Leetcode-120. 三角形最小路径和（动态规划）

120. 三角形最小路径和（动态规划）方法一：自顶向下方法二：自底向上 > 120.三角形最小路径和 > 题目链接：[https://leetcod

一时失言乱红尘/ 2023年02月26日 04:27/ 0 赞/ 171 阅读

相关算法-动态规划-最小路径和

算法-动态规划-最小路径和 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/minimum-path-sum

你的名字/ 2023年02月13日 05:41/ 0 赞/ 45 阅读

相关算法-动态规划-三角形最小路径和

算法-动态规划-三角形最小路径和 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/triangle/ 1

一时失言乱红尘/ 2023年02月12日 14:22/ 0 赞/ 46 阅读

相关三角形最小路径和(动态规划)

> 原创公众号：bigsai 欢迎加入力扣打卡 > 文章已收录在 [全网都在关注的数据结构与算法学习仓库][Link 1] 欢迎star 题目描述 [力扣120原题

今天药忘吃喽~/ 2022年10月28日 14:23/ 0 赞/ 248 阅读

相关坐标型动态规划——最小路径和

给定一个包含非负整数的 `mn` 网格 `grid` ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。 ![在这里插入

Myth丶恋晨/ 2022年10月27日 06:24/ 0 赞/ 150 阅读

相关【leetcode】最小路径和（动态规划）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

柔光的暖阳◎/ 2022年03月06日 10:20/ 0 赞/ 249 阅读