64. 最小路径和

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/minimum-path-sum

题目

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

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

示例:

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

解题思路

思路：动态规划

先审题，因为题目中说明【每次只能向下或者向右移动一步】。那么要到达终点，只能是从终点的上方或者左方到达。

状态定义

设 dp[i][j] 为左上角出发到达位置 (i, j) 的最小路径和

状态转移方程

前面提到，每次移动只能是向下或者向右。对于第一行元素而言（也就是 i = 0 时），只能是从左往右进行移动；对于每一列而言（也就是 j = 0 时），只能是从上往下移动。此时状态转移方程为：

dp[0][j]=dp[0][j−1]+grid[0][j],(i=0andj>0)dp[i][0]=dp[i−1][0]+grid[i][0],(i>0andj=0) \begin{aligned} dp[0][j] = dp[0][j-1] + grid[0][j], \qquad (i = 0\; and\; j > 0) \\ dp[i][0] = dp[i-1][0] + grid[i][0], \qquad (i > 0\; and\; j = 0) \end{aligned} dp[0][j]=dp[0][j−1]+grid[0][j],(i=0andj>0)dp[i][0]=dp[i−1][0]+grid[i][0],(i>0andj=0)​

对于不在第一行第一列的元素，到达位置 (i, j) 只能是从左方向右移动到达或者上方向下移动到达，此时转移方程为：

dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j],(i>0andj>0) \begin{aligned} dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j], \qquad (i > 0 \; and \; j > 0) \end{aligned} dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j],(i>0andj>0)​

状态初始化

dp[0][0] 表示左上角到 (0, 0) 位置的最小路径和，也就是等于二维网格中当前元素的值。也就是：

$dp[0][0]=grid[0][0]$

最终需要求得 dp[m-1][n-1] 的值，表示从左上方到右下方的最小路径和。

具体的代码实现如下。

代码实现

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        m = len(grid)
        n = len(grid[0])

        # 定义 dp 数组
        dp = [[0] * (n) for _ in range(m)]

        # 初始化
        dp[0][0] = grid[0][0]
        # 对第一行和第一列进行处理
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        
        return dp[-1][-1]

实现结果