问题：
题目来源：力扣（LeetCode）
leetcode64.最小路径和
难度：中等
分析： 和不同路径的思路一致。 Tips: 1、本题依旧无法使用辅助行和辅助列，因此乖乖自己初始化第一行和第一列。 2、本题的递推公式为dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]，当前格子值只依赖临近的两个格子的值，因此可以将空间优化到O(n)。
解决方法： 1：二维DP
递推公式为 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: if not r, c = len(grid), len(grid[0]) dp = [[0] * c for _ in range(r)] dp[0][0] = grid[0][0] for i in range(1, r): dp[i][0] = dp[i - 1][0] + grid[i][0] for j in range(1, c): dp[0][j] = dp[0][j - 1] + grid[0][j] for i in range(1, r): for j in range(1, c): dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] #print(dp) return dp[-1][-1]2：空间优化 O(n)
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: if not grid: return 0 r, c = len(grid), len(grid[0]) dp = [0] * c dp[0] = grid[0][0] for j in range(1, c): dp[j] = dp[j - 1] + grid[0][j] for i in range(1, r): dp[0] += grid[i][0] for j in range(1, c): dp[j] = min(dp[j], dp[j - 1]) + grid[i][j] #print(dp) return dp[-1]