leetcode_64_最小路径和

发表于 阅读次数： 本文字数： 539 阅读时长 ≈ 1 分钟
简介：leetcode_64_最小路径和

题目

https://leetcode.cn/problems/minimum-path-sum/description/?envType=study-plan-v2&envId=dynamic-programming

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 行数为m，列数为n
        m,n = len(grid), len(grid[0])

        lst = [[0 for i in range(n)] for j in range(m)]
        lst[m-1][n-1] = grid[m-1][n-1]

        for i in range(m-2,-1,-1):
            lst[i][n-1] = grid[i][n-1]+lst[i+1][n-1]

        for i in range(n-2,-1,-1):
            lst[m-1][i] = grid[m-1][i]+lst[m-1][i+1]
            
        for i in range(m-2,-1,-1):
            for j in range(n-2,-1,-1):
                lst[i][j] = grid[i][j] + min(lst[i+1][j], lst[i][j+1])
                
        return lst[0][0]