Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int M=grid.size();
        int N=grid[0].size();
        if(M==0) return 0;
        vector<vector<int>> res(grid);
        for(int j=1;j<N;j++)    //先要把边界的算出来
            res[0][j]+=res[0][j-1];
        for(int i=1;i<M;i++)
            res[i][0]+=res[i-1][0];
        for(int i=1;i<M;i++)
            for(int j=1;j<N;j++)
            {
                res[i][j]=min(res[i-1][j],res[i][j-1])+res[i][j];
            }
        return res[M-1][N-1];
    }
};