【Leetcode刷题Python】64. 最小路径和
2023-09-14 09:13:00 时间
1 题目
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
2 解析
用一个一位数组来存储每一行到最右下角的最小路径总和,一行存储一个值。
最后返回最后一个元素就是最小路径目标值
3 Python实现
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
dp = [float('inf')]*(len(grid[0])+1)
dp[1] = 0
for row in grid:
for idx,num in enumerate(row):
dp[idx+1] = min(dp[idx],dp[idx+1])+num
return dp[-1]
相关文章
- Python程序在Windows终端乱码解决方法
- 基于Python中numpy数组的合并实例讲解
- Python 刷Leetcode题库,顺带学英语单词(36)
- Python 刷Leetcode题库,顺带学英语单词(24)
- Python语言学习:Python语言学习之python包/库package的简介(模块的封装/模块路径搜索/模块导入方法/自定义导入模块实现华氏-摄氏温度转换案例应用)、使用方法、管理工具之详细攻略
- Python语言学习:利用python获取当前/上级/上上级目录路径(获取路径下的最后叶目录的文件名、合并两个不同路径下图片文件名等目录/路径案例、正确加载图片路径)之详细攻略
- Python语言学习之打印输出那些事:python输出图表和各种吊炸天的字符串或图画、版权声明(如README.md)等之详细攻略
- Python语言学习:利用python获取当前/上级/上上级目录路径(获取路径下的最后叶目录的文件名、合并两个不同路径下图片文件名等目录/路径案例、正确加载图片路径)之详细攻略
- Python编程语言学习:包导入和模块搜索路径(包路径)简介、使用方法(python系统环境路径的查询与添加)之详细攻略
- 【Python成长之路】python 基础篇 -- global/nonlocal关键字使用
- python sanic中文参考资料
- 【LeetCode Python实现】673. 最长递增子序列的个数(中等)
- python 将一个JSON 字典转换为一个Python 对象
- python 将字节写入文本文件
- 【Leetcode刷题Python】473. 火柴拼正方形
- 【Leetcode刷题Python】16. 最接近的三数之和
- 【Leetcode刷题Python】104. 二叉树的最大深度
- 【Leetcode刷题Python】滑雪路径消耗时间:Testing Round #16 (Unrated) C. Skier
- 【Leetcode刷题Python】416. 分割等和子集
- 【Python】.tsp文件的读取