64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

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

思路：典型的动态规划题目，设置dp[m][n]，表示走到该位置的最小路径和。机器人每次只能向下或者向右移动一步，状态转移方程：dp[i][j]=min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，注意边界。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        for(int i=0; i<grid.size(); ++i){
            for(int j=0; j<grid[i].size(); ++j){
                if(i==0 && j==0) continue;
                else if(i==0) grid[i][j]=grid[i][j-1]+grid[i][j];
                else if(j==0) grid[i][j]=grid[i-1][j]+grid[i][j];
                else{
                    grid[i][j]=min(grid[i-1][j], grid[i][j-1])+grid[i][j];
                }   
            }
        }
        return grid[grid.size()-1][grid[0].size()-1];
    }
};