最小路径和python_python左右两侧移动,找最小路径

解题思路，该题和在棋盘上移动的题目具有相似的解法，只不过本题在路径的基础上加入判断，判断能到达当前网格路径的最小值。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        m= len(grid)  #m列
        n =len(grid[0])  #n行

        #创建一个二维数组
        dp = [[0]*n for _ in range(m)]

        #初始化左上角
        dp[0][0] = grid[0][0]
        #初始化第一列,最小和只能从上面到达，且需要加上当前格子的元素值
        for i in range(1,m):
            dp[i][0] = dp[i-1][0]+grid[i][0]
        #初始化第一行，最小和只能从左边到达，且需要加加上当前格子元素的最小值
        for i in range(1,n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        
        #遍历其他地方的格子,路径只能从相邻左方和相邻上方到达，然后比较两者中最小的元素值加上当前网格的值
        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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25