最小路径和

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

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解题思路：
这是一道典型的动态规划问题，如果你不知道什么是动态规划，可以查看下面这篇文章，可谓深入浅出，非常好。
https://www.sohu.com/a/153858619_466939
回到这道题，先写出状态转移方程：
A[m][n]=min(A[m-1][n],A[m][n-1])+grid[m][n]
A表示左上角到该点的最小距离。
临界条件就是不能超出原矩阵的长宽范围。
我们可用一个m*n的二维矩阵来记录原矩阵中左上角到每个点的最小距离。
不过这道题里，只要到右下角的最小距离，在我们的状态转移方程中，只需要当前行和上一行就够了。所以，不需要保存所有距离，只用保存一行就够了然后不断更新这一行就可以了。
代码如下：

    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        dp=grid[0]
        for i in range(1, len(grid[0])):
            dp[i]=dp[i - 1] + dp[i]
        for i in range(1, len(grid)):
            dp[0] += grid[i][0]
            for j in range(1, len(grid[0])):
                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
        return dp[-1]