第63题的变化版本，同样可以通过使用动态规划思想来解决。

题目

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

考察知识点

动态规划

核心思想

和第63题的思路一模一样，第一列各个位置的和只能从最左上角那个位置的值往下相加得到，同理，第一行各个位置的和也只能从最左上角那个位置的和往右相加得到，这样就可以先求解第一行和第一列各个位置上的值。再动态规划每一个位置最小值，一直递归到右下角最后一个位置。

Python版本

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])

        if m == 0 or grid == 0:
            return 0
        if m == 1 and n == 1:
            return grid[0][0]

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

        return grid[-1][-1]


print("leet code accept!!!")
Input = [
    [
        [1,3,1],
        [1,5,1],
        [4,2,1]
    ]
]
Input1 = [2, 3]
Answer = [7]


if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.minPathSum(Input[i])
        print(reslut == Answer[i])

时间复杂度：\(O(m \times n)\) 。
空间复杂度：$O(1)，除了求解 n 和 m 以外，没有使用额外的空间。
执行用时 :60 ms, 在所有 Python3 提交中击败了86.00%的用户。
内存消耗 :14.9 MB, 在所有 Python3 提交中击败了6.25%的用户。