[动态规划]Leetcode64.最小路径和(python)

简介: [动态规划]Leetcode64.最小路径和(python)

[动态规划]Leetcode64.最小路径和


如果读者对于动态规划思路解法还不是很了解,可以先点击链接查阅我之前的一篇博文《算法之【动态规划】详解》,很详细的介绍了动态规划求解思路及方法,有利于你更好的学习动态规划。


题目描述


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


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


示例1


20201205203639755.png


输入:grid = [[1,3,1],[1,5,1],[4,2,1]]

输出:7

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


DP定义及状态方程


定义dp[i][j]表示到达(i,j)坐标处的最小路径和,达到(i,j)处只能通过两条路(i-1,j)与(i,j-1),选择其中路径和最小的一个即可,因此递推方程为dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + gird[i][j]


此题目的最终答案即为dp数组中的最后一个值:dp[-1][-1]


初始边界条件


初始化过程,对于第一列从上往下走,第一行只能从左往右走:因此dp[i][0]=dp[i-1][0]+grid[i][0], dp[0][j]=dp[0][j-1]+grid[0][j]


#初始化边界条件
dp[0][0] = grid[0][0]
for i in range(1, m):
    dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
    dp[0][j] = dp[0][j-1] + grid[0][j]


最终代码


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
        return dp[-1][-1]
相关文章
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
99 0
|
5月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
265 14
|
6月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
132 4
|
6月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
148 10
|
数据采集 Python
Python实用记录(七):通过retinaface对CASIA-WebFace人脸数据集进行清洗,并把错误图路径放入txt文档
使用RetinaFace模型对CASIA-WebFace人脸数据集进行清洗,并将无法检测到人脸的图片路径记录到txt文档中。
276 1
|
6月前
|
机器学习/深度学习 算法 Go
【LeetCode 热题100】139:单词拆分(动态规划全解析+细节陷阱)(Go语言版)
本题是 LeetCode 热题 139:单词拆分(Word Break),需判断字符串 `s` 是否能由字典 `wordDict` 中的单词拼接而成。通过动态规划(DP)或记忆化搜索解决。DP 中定义布尔数组 `dp[i]` 表示前 `i` 个字符是否可拆分,状态转移方程为:若存在 `j` 使 `dp[j]=true` 且 `s[j:i]` 在字典中,则 `dp[i]=true`。初始条件 `dp[0]=true`。代码实现中用哈希集合优化查找效率。记忆化搜索则从起始位置递归尝试所有切割点。两种方法各有利弊,DP 更适合面试场景。思考扩展包括输出所有拆分方式及使用 Trie 优化大字典查找。
166 6
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
93 0
|
11月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
214 2
|
12月前
|
存储 算法 Python
【10月更文挑战第16天】「Mac上学Python 27」小学奥数篇13 - 动态规划入门
本篇将通过 Python 和 Cangjie 双语介绍动态规划的基本概念,并解决一个经典问题:斐波那契数列。学生将学习如何使用动态规划优化递归计算,并掌握编程中的重要算法思想。
210 3
|
IDE 开发工具 iOS开发
Python编程案例:查找指定文件大小的文件并输出路径
Python编程案例:查找指定文件大小的文件并输出路径
298 3

推荐镜像

更多