64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入: [[1,3,1],[1,5,1],[4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
解题思路：
1.确定状态
- dp[i][j] 表示到达第 i 行、第 j 列的最短路径和。
2.转移方程
3.边界情况
- 第一列——
- 第一行——
程序代码（Python）：
class Solution:def minPathSum(self, grid):m = len(grid)n = len(grid[0])for i in range(1,m):grid[i][0] += grid[i-1][0]for i in range(1,n):grid[0][i] += grid[0][i-1]for i in range(1,m):for j in range(1,n):grid[i][j] = grid[i][j] + min(grid[i-1][j],grid[i][j-1])return grid[m-1][n-1]grid = [[1,2,5],[3,2,1]]
s = Solution()
print(s.minPathSum(grid))
程序代码（C++）：
class Solution {
public:int minPathSum(vector<vector<int> >& grid)
{int n = grid.size();int m = grid[0].size();if(n==0&&m==0)return 0;//初始化第一行for(int i=1;i<m;i++){grid[0][i] += grid[0][i-1];}//初始化第一列for(int i=1;i<n;i++){grid[i][0] += grid[i-1][0];}for(int i=1;i<n;i++){for(int j=1;j<m;j++){grid[i][j] += min(grid[i-1][j],grid[i][j-1]);}}return grid[n-1][m-1];
}
};