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]

实现后果

欢送关注

公众号 【书所集录】