Daily LeetCode 64. Minimum Path Sum

https://leetcode.com/problems/minimum-path-sum/

Medium

问题描述：

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路及代码：

这一题給定了一个附带权值的grid，左上角为起点，右下角为终点，每次向下或者向右走，要求寻找一条权值之和最小的路径，并返回最小权值和。

我们可以通过一个二维数组dp[i][j]来保存从起点到[i,j]位置的最小权值和，状态转移方程如下：

dp[i][j] = min(grid[i][j] + dp[i-1][j], grid[i][j] + dp[i][j-1])

最后我们返回dp[-1][-1]即可。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        row = len(grid)
        column = len(grid[0])
        dp = [[0] * column for _ in range(row)]
        print(grid[-1][0])
        for i in range(row):
            for j in range(column):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0:
                    dp[i][j] = grid[i][j] + dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = grid[i][j] + dp[i - 1][j]
                else:
                    dp[i][j] = min(grid[i][j] + dp[i][j - 1], grid[i][j] + dp[i - 1][j])

        return dp[row - 1][column - 1]        

这一题可以直接在题目给定的grid上修改，从而降低空间复杂度，同时，对第一列和第一行单独处理：

def minPathSum(self, grid):
    m = len(grid)
    n = len(grid[0])
    for i in range(1, n):
        grid[0][i] += grid[0][i - 1]
    for i in range(1, m):
        grid[i][0] += grid[i - 1][0]
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
    return grid[-1][-1]