Beats 100% with O(n) space

• ``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> dp(n);

dp[0] = grid[0][0];
for (int j = 1; j < n; j++) {   // init
dp[j] = dp[j-1] + grid[0][j];
}

for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[j] = (j == 0 ? dp[j] : min(dp[j], dp[j-1])) + grid[i][j];
}
}
return dp[n-1];
}
};
``````

In usual provide O(mn) solution first, then try to optimize it. From dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j], you can see it only depends on previous row and current row value, we waste a lot space if use mn space.

dp[i][j] is row i, column j;
dp[i][j-1] is row i, column j-1;
dp[i-1][j] is row i-1, column j;

if we just use row to represent dp[i], then it should be

row[j] = min(row[j-1], row[j]) + grid[i][j];

why dp[i-1][j] is row[j], because before we set new value for row[j], it saves old value, which is dp[i-1][j].

So the new transition formula is:

row[j] = min(row[j-1], row[j]) + grid[i][j];

still use dp variable to replace row, it is:

dp[j] = min(dp[j-1], dp[j]) + grid[i][j];

variable j is from 0 to n, same as before. But the i is not used in two dimension row number, just use iteration number. We need do m-1 iterations, because we don't need do it for first row, which is init value.

• If I dont use extra space, I do the dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j] on the existing grid: grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]); I think they are the same, but the run time of your solution is much better. I dont know why. would you please tell me the reason?

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