【算法题】64. 最小路径和-力扣(LeetCode)

1.题目

下方是力扣官方题目的地址

64. 最小路径和

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

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

示例 1：

[1,3,1]
[1,5,1]
[4,2,1]

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

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

2.题解

思路

这题和力扣第120题120. 三角形最小路径和非常相似，都是求最小路径和，一个是在三角形中一个是在矩阵中。

大家有兴趣也可以看看我的关于力扣第120题的题解【算法题】120. 三角形最小路径和-力扣(LeetCode)

三角形那题是求从三角形最顶端走到三角形最低端的最小路径和；而本题是从矩阵的左上角走到右下角的最小路径和。

三角形的那题每一步只能移动到下一行中相邻的结点上;而本题要求每次只能向下或者向右移动一步。

这两个要求分别蕴藏着每一步与上一步或者上一步之间的关系。

而上一步与下一步有着联系，我们可以比较容易的想到这题可以用到动态规划。

而动态规划的核心步骤就是找到状态转移方程，而状态转移方程就隐藏在这些要求之中

我们以grid = [[1,3,1],[1,5,1],[4,2,1]]为例：

[1,3,1]
[1,5,1]
[4,2,1]

由于只能向右或者下走，反过来，比如说你想要到达（1，1）这个位置，即5的位置，你必须得经过（0，1）即3这个位置或者（1，0)即1这个位置。

这题和三角形那题一样，也有一些比较特殊的地方：第一列元素和第一行元素：第一列元素只能由上方来；第一行元素只能由左方来，而第一个元素既不能从左边来也不能从上边来。

考虑到这些，我们用dp[i] [j] 表示从左上角出发到 (i,j) 位置的最小路径和。

结合下方的dp图：

在这里插入图片描述

就很容易地可以得出状态转移方程：

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]

至于这些前面谈到的特殊元素，因为它们的路径都是固定只有一个点可以到达，所以我们可以直接给它们赋上值：

for i in range(1,n):
    dp[0][i]=dp[0][i-1]+grid[0][i]
for j in range(1,m):
    dp[j][0]=dp[j-1][0]+grid[j][0]

Python代码

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m,n=len(grid),len(grid[0])
        dp=[[0]*n for _ in range(m)]                # 初始化dp数组
        dp[0][0]=grid[0][0]
        for i in range(1,n):
            dp[0][i]=dp[0][i-1]+grid[0][i]          # 直接给特殊元素赋上值
        for j in range(1,m):
            dp[j][0]=dp[j-1][0]+grid[j][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]