# C++ dp solutions (O(m*n) and O(n) space).

• ``````// 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];
}``````

• You can reduce the `O(m*n)` solution to `O(1)` space, just change `dp = grid` to `&dp = grid` ;)
What do you think about this kind of `O(1)` solutions in general?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.