步骤一、确定状态:

1、确定原问题中变化的变量个数 2、考虑最后一步
右下角坐标设为(m-1,n-1) 那么前一步一定是在(m-2,n-1)或者(m-1,n-2)

步骤二、推断状态方程:

f[i][j] =从(0,0)走到(i,j)的路径最小数字总和

步骤二、推断状态方程:

f[i][j] =从(0,0)走到(i,j)的路径最小数字总和 A[i][j] 格子(i,j)的数字
f[i][j] = min{f[i-i][j],f[i][j-1]}+A[i][j]

步骤三、规定初始条件和边界:

初始条件:
f[0][0]=A[0][0] 边界情况:i=0或j=0，前一步只有一个方向能过来

步骤四、计算顺序:

自底向上
先计算第0行，f[0][0] ....f[0][n-1] 计算第1行: f[1][0] ....f[1][n-1]
...
计算第m-1行: f[m-1][0] ....f[m-1][n-1]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid:
            return 

        m, n = len(grid), len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[0][0] = grid[0][0]

        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][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-1][j], dp[i][j-1]) + grid[i][j]


        return dp[-1][-1]