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 时），只能是从上往下挪动。此时状态转移方程为：

$$
\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}
$$

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

$$
\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[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]

实现后果

欢送关注

公众号【书所集录】