64. 最小路径和 [medium]

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

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

通过次数128,847 | 提交次数191,133

First Try

2020-07-29

本来打算用遍历，但发现还是可以用dp来完成，跟前面62，63题差不多.

dp[m][n] = min(dp[m][n-1], dp[m-1][n)] + grip[m][n]

特别注意点：如果m, n超出了范围，那么应该返回的是无穷大，而不是0，否则这条不应该存在的路线由于min(dp[m][n-1], dp[m-1][n)]取小值，会被选择为正确的路线。

DP类型的题目都是第一眼看上去有点懵逼，暴力遍历复杂度爆表，但是想清楚了迭代之间的关系，再找个起始点，又是手到擒来。这类题目真是最适合计算机来解决了，如果手算找公式会很头疼。

不过目前的dp类型都是数值汇总类，只要答案不追求过程。如果要求得到最短的实际路径，又要麻烦一些，需要在算min的时候附带上路径。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 本来打算用遍历，但发现还是可以用dp来完成，跟前面62，63题差不多
        # dp[m][n] = min(dp[m][n-1], dp[m-1][n)] + grip[m][n]
        if not (len(grid) and len(grid[0])):
            return 1 
        m, n = len(grid), len(grid[0])
        dp = [[""] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        def path(m, n):
            if m < 0 or n < 0:
                # return 0
                return float('inf') # 应该选择无限大，而不是0, 不然这条不存在的路会被选择上
            if dp[m][n] != "":
                return dp[m][n]
            dp[m][n] = min(path(m, n - 1), path(m - 1, n)) + grid[m][n]
            return dp[m][n]
        
        return path(m - 1, n - 1)

执行用时：76 ms, 在所有 Python3 提交中击败了15.12%的用户
内存消耗：15.6 MB, 在所有 Python3 提交中击败了8.33%的用户

64. 最小路径和 [medium]​

First Try​

64. 最小路径和 [medium]

First Try