```
// O(m*n) space
int minPathSum1(vector<vector<int>>& grid) {
vector<vector<int>> dp = grid;
int row = dp.size(), col = dp[0].size();
for (unsigned int i = 1; i < row; i++)
dp[i][0] += dp[i-1][0];
for (unsigned int j = 1; j < col; j++)
dp[0][j] += dp[0][j-1];
for (unsigned int i = 1; i < row; i++)
for (unsigned int j = 1; j < col; j++)
dp[i][j] += min(dp[i-1][j], dp[i][j-1]);
return dp[row-1][col-1];
}
// O(n) space
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();
vector<int> dp = grid[0];
for (unsigned int j = 1; j < col; j++)
dp[j] += dp[j-1];
for (unsigned int i = 1; i < row; i++) {
dp[0] += grid[i][0];
for (unsigned int j = 1; j < col; j++)
dp[j] = grid[i][j] + min(dp[j-1], dp[j]);
}
return dp[col-1];
}
```