【每日算法】2021年03月31日小雨最小路径和

字数统计: 422阅读时长: 1 min

 2021/04/01 

这道题是LeeCode第64题，和之前的第62题一样，属于动态规划中的中等难度题目。

题目

解题思路

本题的解题思路和之前的第62题很相似，定义dp[i][j]为从第(i, j)点走到右下角的最短路径，则有dp[i][j] = dp[i+1][j] + dp[i][j+1].

然后我们来考虑边界条件，此题的边际和第62题的边际一样，不同的是边界上面dp值，当在下边界的时候dp[m-1][j] = sum(gird[m-1][j:-1]), 在左边界的时候
dp[i][n-1] = sum(grid[i:-1][n-1])， dp[m-1][n-1] = grid[m-1][n-1].

最终答案为: dp[0][0]

实现代码

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for i in range(n)] for j in range(m)] #这里纠结了不少时间
        for j in range(n-1, -1, -1):
            dp[m-1][j] = sum(grid[m-1]) - sum(grid[m-1][0:j]) 
        col = [x[n-1] for x in grid]
        for i in range(m-1, -1, -1):
            dp[i][n-1] = sum(col)-sum(col[0:i])
        for i in range(m-2, -1, -1):
            for j in range(n-2, -1, -1):
                dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1])
        return dp[0][0]