题目链接
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.
解题思路
TODO （稍后补充）
解答代码
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
int sum=0;
vector<vector<int> > minMatrix(grid.size(), vector<int>(grid[0].size(), 0));
int zeroSum = 0;
for(int i=0;i<grid[0].size();i++) {
zeroSum += grid[0][i];
minMatrix[0][i] = zeroSum;
}
zeroSum = 0;
for(int i=0;i<grid.size();i++) {
zeroSum += grid[i][0];
minMatrix[i][0] = zeroSum;
}
for(int i=1;i<grid.size();i++) {
for(int j=1;j<grid[i].size();j++) {
minMatrix[i][j] = minMatrix[i-1][j] >= minMatrix[i][j-1] ? minMatrix[i][j-1]+grid[i][j] : minMatrix[i-1][j]+grid[i][j];
}
}
return minMatrix[grid.size()-1][grid[0].size()-1];
}
};
