LeetCode Minimum Path Sum

LeetCode解題之Minimum Path Sum

原題

從一個矩陣的左上角出發到右下角，只能向右或向下走，找出哪一條路徑上的數字之和最小。

注意點：

例子：

輸入:
[
[1, 2, 4],
[2, 4, 1],
[3, 2, 1]
]

輸出: 9

解題思路

思路跟 Unique Paths 相似，不過從計算到達該點有多少種走法轉變為求最小和為多少。找出上面和左邊格子的最小值加上當前格子中的數字即可。為了節省空間，把二維dp降為一維的，因為是求最優解，前面的中間值可以拋棄。

AC源碼

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])

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


if __name__ == "__main__":
    assert Solution().minPathSum([
        [1, 2, 4],
        [2, 4, 1],
        [3, 2, 1]]) == 9