class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int rows = grid.size();
int columns = grid[0].size();
int res = 0;
int dp[1000][1000]={0};
if(rows <1 || columns <1){
return 0;
}
if(rows == 1 && columns == 1){
return grid[0][0];
}
if(rows == 1 && columns != 1){
for(int i = 0 ; i < columns ; i++){
res = res + grid[0][i];
}
return res;
}
if(columns == 1 && rows !=1){
for(int j = 0; j<rows ;j++){
res = res + grid[j][0];
}
return res;
}
dp[0][0] = grid[0][0];
for(int k = 1 ;k<rows;k++){
dp[k][0] = dp[k-1][0] + grid[k][0];
}
for(int y = 1; y< columns ;y++){
dp[0][y] = dp[0][y-1]+grid[0][y];
}
dp[1][0] = grid[0][0]+grid[1][0];
dp[0][1] = grid[0][0]+grid[0][1];
for(int j = 1 ; j < rows ; j++){
for(int k = 1 ; k < columns ; k++){
dp[j][k] = min(dp[j-1][k] + grid[j][k],dp[j][k-1] + grid[j][k]);
}
}
return dp[rows-1][columns-1];
}
};
这道题需要先处理好边界条件，当只有一行或者一列的情况就是将这一行相加，还有计算到每个点的和，每次都是基于最小的那个值，对于每个位置它只能基于当前节点的左侧或者上策走过来，所以选择这两个方案中和较小的那条路加上当前未知的值就是，最小路径和了。
