64. Minimum Path Sum

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

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.

Thoughts

走格且求最优结果，DP。action为从上面下来和从左边过来。优化空间时要在循环里初始化第0列的结果。

Code

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        M = len(grid)
        if M == 0:
            return 0
        N = len(grid[0])
        dp = [0] * 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[N - 1]