LC 64最小路径和Minimum Path Sum　中等

网格每格带非负权值，从左上走到右下每步只能右移或下移，求路径权值和的最小值。

思路 一行 DP：dp[j] = min(上方 dp[j], 左方 dp[j-1]) + 格子值，逐行滚动。时间 O(mn)。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [inf] * n
        dp[0] = 0
        for row in grid:
            dp[0] += row[0]
            for j in range(1, n):
                dp[j] = min(dp[j], dp[j - 1]) + row[j]
        return dp[-1]