给定一个包含非负整数的 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]