题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个二维数组，要找出一条路径从左上往右下的数值最小。

思路分享

  • 以后对于动态规划问题，第一个念头应该是尝试拆分为子问题，该问题换个说法就是找出 m,n 的二维数组中的最短路，这个结果可以由 m-1,n 和 m,n-1 这两个子问题推导出来（因为题目规定了每次只能向下或向右走）

  • 那么就很容易得出状态转换公式：f[i+1][j+1] = min(f[i+1][j], f[i][j+1])+grid[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:
        m = len(grid)
        n = len(grid[0])
        
        for i in range(m-1):
            grid[i+1][0] += grid[i][0]
        for j in range(n-1):
            grid[0][j+1] += grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        # print(grid)
        return grid[m-1][n-1]