64. 最小路径和

一、64. 最小路径和 1.1、题目描述

1.2.1、动态规划

我们新建一个额外的 dp 数组，与原矩阵大小相同。在这个矩阵中，dp(i,j) 表示从坐标 (i, j)到右下角的最小路径权值。我们初始化右下角的 dp 值为对应的原矩阵值，然后去填整个矩阵，对于每个元素考虑移动到右边或者下面，因此获得最小路径和我们有如下递推公式：dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1))

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # dp[i][j] 表示坐标(i, j)到右下角的最小距离
        dp = [[0] * n for _ in range(m)]
        
        # 注意从右下角往左上角遍历
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if i == m-1 and j != n-1:   # 最后一列
                    dp[i][j] = grid[i][j] + dp[i][j+1]
                elif i != m-1 and j == n-1: # 最后一行
                    dp[i][j] = grid[i][j] + dp[i+1][j]
                elif i != m-1 and j != n-1:
                    dp[i][j] = grid[i][j] + min(dp[i][j+1], dp[i+1][j])
                else:   # 最右下角
                    dp[i][j] = grid[i][j]
        return dp[0][0]

1.2.2、一维动态规划

使用一维数组存储前一行每个元素都右下角的最小位置， 下一行的元素通过下方和右边来更新距离dp(j)=grid(i,j)+min(dp(j),dp(j+1)), 向上移动。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # dp[j] 表示坐标(i, j)到右下角的最小距离
        dp = [0] * n
        # 注意从右下角往左上角遍历
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if i == m-1 and j != n-1:   # 最后一行
                    dp[j] = grid[i][j] + dp[j+1]
                elif i != m-1 and j == n-1: # 最后一列
                    dp[j] = grid[i][j] + dp[j]
                elif i != m-1 and j != n-1:
                    dp[j] = grid[i][j] + min(dp[j+1], dp[j])
                else:   # 最右下角
                    dp[j] = grid[i][j]
        return dp[0]

1.2.3、不适用额外空间

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        
        # 注意从右下角往左上角遍历
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if i == m-1 and j != n-1:   # 最后一列
                    grid[i][j] = grid[i][j] + grid[i][j+1]
                elif i != m-1 and j == n-1: # 最后一行
                    grid[i][j] = grid[i][j] + grid[i+1][j]
                elif i != m-1 and j != n-1:
                    grid[i][j] = grid[i][j] + min(grid[i][j+1], grid[i+1][j])
                else:   # 最右下角
                    grid[i][j] = grid[i][j]
        return grid[0][0]