给定一个包含非负整数的m x n网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
- 示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
# -*- coding：utf-8 -*-
# &Author AnFany
# 64_Minimum_Path_Sum 最小路径和
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# 利用动态规划的方法
# 要到达索引为[r,l]的网格
# 一是从[r,l-1]的网格向右走过来的
# 二是从[r-1,l]的网格向下过来的
# 令S[r,l]表示到达索引为[r,l]的网格的最短路径
# 则动态规划的状态转移方程为S[r,l] = min(S[r-1,l], S[r,l-1]) + grid[r,l]
m, n = len(grid), len(grid[0]) # 网格的行数和列数
if not m: # 行列为0
return 0
# 存储最短的路径的数组。只需要2行即可
# 开始利用动态规划寻找最小路径
for r in range(m):
for l in range(n):
# 对于边界之外的网格，令该网格的数为正无穷大
if r >= 1 and l >= 1:
grid[r][l] = grid[r][l] + min(grid[r - 1][l], grid[r][l - 1])
elif r >= 1:
grid[r][l] = grid[r][l] + grid[r - 1][l]
elif l >= 1:
grid[r][l] = grid[r][l] + grid[r][l - 1]
return grid[-1][-1]