64. 最小路径和
Difficulty: 中等
给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
Solution
这个算是比较简单类型的动态规划题目了，题目要求从网格中找到一条从左上角到右下角的路径，并且每次只能向右或者向下移动，所以到达网格中grid[i][j]只会以下几种情况：
- 当i=0或j=0时，此时在网格的边缘处，此时只能向右或者只能向下移动
- 当i>0且j>0时，此时不在网格的边缘处，那么到达
grid[i][j]可以是从它的上方或者左方方向，此时我们只需要取路径和较小的方向即可
时间复杂度O(mn)，没有使用额外的空间。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# m 矩阵行数 n 矩阵列数
m, n = len(grid), len(grid[0])
if m == 0 or n == 0:
return 0
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
elif i > 0 and j == 0:
grid[i][j] += grid[i-1][j]
elif i == 0 and j > 0:
grid[i][j] += grid[i][j-1]
else:
grid[i][j] += min(grid[i-1][j],grid[i][j-1])
return grid[m-1][n-1]
相似题目：