LeetCode--064--最小路径和
2024-10-07 07:17:12
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思路:dp思想,为每个点构造最短路径矩阵,每次看左边和上边的最短路径,最小的那个加上该位置的值,就是到达该位置的最短路径。
由于是两层for,时间复杂度比较高
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if len(grid) == 0:return 0
res = [[99 for n in range(len(grid[0]))] for m in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == 0 and j == 0:
res[i][j] = grid[i][j]
elif i == 0 and j != 0:
res[i][j] = res[i][j-1] + grid[i][j]
elif i != 0 and j == 0:
res[i][j] = res[i-1][j] + grid[i][j]
else:
res[i][j] = min(res[i-1][j],res[i][j-1]) + grid[i][j]
return res[-1][-1]
提交的最快的一种:
□ √ √ 第一行的√,依赖于其左边的 第一列的√依赖于其上面的,先算出来,直接在原矩阵计算就行,空间复杂度降了
√ □ □
√ □ □
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int: for i in range(1,len(grid)):
grid[i][0]+=grid[i-1][0]
for i in range(1,len(grid[0])):
grid[0][i]+=grid[0][i-1] for i in range(1,len(grid)):
for j in range(1,len(grid[0])):
grid[i][j]=min(grid[i-1][j]+grid[i][j], grid[i][j-1]+grid[i][j]) return grid[-1][-1]
最新文章
- 请写一个php函数,可以接受任意数量的参数
- Django 1.10 中文文档------3.2.1 模型Models
- hdu1166 线段树
- dubbo源码之三-模块依赖
- Java基础01 ------ 从HelloWorld到面向对象
- 浩哥解析MyBatis源码(三)——Transaction事务模块
- 在Eclipse如何实现在xml文件实现代码提示
- 完整版ajax+百度echarts实现统计图表demo并随着窗口大小改变而自适应
- 浅析 jQuery 内部架构设计
- es6冲刺02
- java语言规范,main方法必须声明为public
- Linux工作中常用命令
- Note | Markdown
- D3.js的一些基础部分 (v3版本)
- sass 的安装 编译 使用
- virtualBox导入虚拟机启动报错
- 【转】java并发编程系列之ReadWriteLock读写锁的使用
- Python 中的线程-进程2
- nginx upstream 名称下划线问题
- 6,synchronized, lock 区别