64. 最小路径和

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

解法一：dp

在62、63题基础上，由“累加”性质很容易想到dp方程：dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]，即(i, j)处的最小和可以由左边、上边的最小值加上此处的值而得。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n for _ in range(m)]  #状态表
        dp[0][0] = grid[0][0]  #初始条件
        #第0列
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        #第0行
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        #填表
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
        return dp[m-1][n-1]