LeetCode--064--最小路径和

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

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

示例:

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

 

思路:dp思想,为每个点构造最短路径矩阵,每次看左边和上边的最短路径,最小的那个加上该位置的值,就是到达该位置的最短路径。

由于是两层for,时间复杂度比较高

 1 class Solution:
 2     def minPathSum(self, grid: List[List[int]]) -> int:
 3         if len(grid) == 0:return 0
 4         res = [[99 for n in range(len(grid[0]))] for m in range(len(grid))]
 5         for i in range(len(grid)):
 6             for j in range(len(grid[0])):
 7                 if i == 0 and j == 0:
 8                     res[i][j] = grid[i][j]
 9                 elif i == 0 and j != 0:
10                     res[i][j] = res[i][j-1] + grid[i][j]
11                 elif i != 0 and j == 0:
12                     res[i][j] = res[i-1][j] + grid[i][j]
13                 else:
14                     res[i][j] = min(res[i-1][j],res[i][j-1]) + grid[i][j]
15         return res[-1][-1]
16         
17         

提交的最快的一种:

□  √  √      第一行的√,依赖于其左边的   第一列的√依赖于其上面的,先算出来,直接在原矩阵计算就行,空间复杂度降了

√ □  □ 

√ □  □ 

 1 class Solution:
 2     def minPathSum(self, grid: List[List[int]]) -> int:
 3         
 4         for i in range(1,len(grid)):
 5             grid[i][0]+=grid[i-1][0]
 6         for i in range(1,len(grid[0])):
 7             grid[0][i]+=grid[0][i-1]
 8         
 9         for i in range(1,len(grid)):
10             for j in range(1,len(grid[0])):
11                 grid[i][j]=min(grid[i-1][j]+grid[i][j], grid[i][j-1]+grid[i][j])
12         
13         return grid[-1][-1]

 

上一篇:Java学习-064-Springboot 解决跨域访问简单配置示例


下一篇:L1-064 估值一亿的AI核心代码 (20分) 团体程序设计天梯赛-练习集