64-最小路径和

Leetcode题解
  1. 64、最小路径和
    1. 题目：
    2. 题解：

64、最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

题目：

aho1hV.png

题解：

此题和63、62相同类型，动态规划，把一个大问题分解成相互独立的若干个小问题。把求起点到终点的最短路径，分解为到终点(i，j)的最短距离Q(i，j)= min（Q(i-1，j)，Q(i，j-1)）+ Q(i，j)，因为只能向右走或者向左走！

所以我们可以进行第0行和第0列的初始化，因为机器人只能向右或者向下走，所以到达第0行，和第0列每个点的最小路径和一定是固定的。比如说第0行，要想到达第0行的任一元素，就必须从该元素的左边走过去；第0列也同样，必须从该元素的上面下来。

进行初始化后，我们就可以遍历所有点，进行Q(i，j)= min（Q(i-1，j)，Q(i，j-1)）+ Q(i，j)的计算，最后得到最小路径和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        for i in range(n):
            if i != 0:
                grid[i][0] += grid[i-1][0]
        for i in range(m):
            if i != 0:
                grid[0][i] += grid[0][i-1]
        for i in range(1, n):
            for j in range(1, m):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[n-1][m-1]

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器