10-lines 28ms O(n)-space DP solution in C++ with Explanations

• This is a typical DP problem. Suppose the minimum path sum of arriving at point `(i, j)` is `S[i][j]`, then the state equation is `S[i][j] = min(S[i - 1][j], S[i][j - 1]) + grid[i][j]`.

Well, some boundary conditions need to be handled. The boundary conditions happen on the topmost row (`S[i - 1][j]` does not exist) and the leftmost column (`S[i][j - 1]` does not exist). Suppose `grid` is like `[1, 1, 1, 1]`, then the minimum sum to arrive at each point is simply an accumulation of previous points and the result is `[1, 2, 3, 4]`.

Now we can write down the following (unoptimized) code.

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int> > sum(m, vector<int>(n, grid[0][0]));
for (int i = 1; i < m; i++)
sum[i][0] = sum[i - 1][0] + grid[i][0];
for (int j = 1; j < n; j++)
sum[0][j] = sum[0][j - 1] + grid[0][j];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
sum[i][j]  = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
return sum[m - 1][n - 1];
}
};
``````

As can be seen, each time when we update `sum[i][j]`, we only need `sum[i - 1][j]` (at the current column) and `sum[i][j - 1]` (at the left column). So we need not maintain the full `m*n` matrix. Maintaining two columns is enough and now we have the following code.

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> pre(m, grid[0][0]);
vector<int> cur(m, 0);
for (int i = 1; i < m; i++)
pre[i] = pre[i - 1] + grid[i][0];
for (int j = 1; j < n; j++) {
cur[0] = pre[0] + grid[0][j];
for (int i = 1; i < m; i++)
cur[i] = min(cur[i - 1], pre[i]) + grid[i][j];
swap(pre, cur);
}
return pre[m - 1];
}
};
``````

Further inspecting the above code, it can be seen that maintaining `pre` is for recovering `pre[i]`, which is simply `cur[i]` before its update. So it is enough to use only one vector. Now the space is further optimized and the code also gets shorter.

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> cur(m, grid[0][0]);
for (int i = 1; i < m; i++)
cur[i] = cur[i - 1] + grid[i][0];
for (int j = 1; j < n; j++) {
cur[0] += grid[0][j];
for (int i = 1; i < m; i++)
cur[i] = min(cur[i - 1], cur[i]) + grid[i][j];
}
return cur[m - 1];
}
};``````

• thank you for explanations~ idea is rather concise and good.

• Hi, scimagian. You are very welcome :-)

• This post is deleted!

• I hope for a future where all discuss posts are like this!

• The process of optimization is excellent!

• How can we modify the O(n) space code if we are allowed to move in diagonal direction also ?

• If you move diagonal you need `pre[i-1][j-1]` so you need to maintain an extra `int` variable which holds that. You can declare and initialize it inside every `j` iteration and use/update in every `i` iteration.

• Another concise solution,

``````int minPathSum(vector<vector<int>>& g) {

m = g.size();
if (m == 0) return 0;

n = g[m-1].size();

vector <vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));
dp[0][1] = 0;

for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + g[i-1][j-1];
}
}

return dp[m][n];
}``````

• Another concise solution. Only 12ms and beat 100%.

``````int m = grid.size(), n = grid[0].size();
vector<int> curV(m+1, INT_MAX);
curV[0] = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
curV[j+1] = grid[j][i]+min(curV[j+1], curV[j]);
curV[0] = curV[1];
}
}
return curV[m];``````

• excellent ,amazing , thanks for share .

• @jianchao.li.fighter What can I say? Just awesome, quite fetching explanation and charming code. Thank you so much!

• Just re-coded your last solution using C++.

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid)
{
int rowSize = grid.size();
if(rowSize == 0) return 0;
int colSize = grid[0].size();
int cur[colSize]{0};
partial_sum(grid[0].begin(), grid[0].end(), cur);
for(int r = 1; r < rowSize; ++r)
{
cur[0] += grid[r][0];
for(int c = 1; c < colSize; ++c)
cur[c] = min(cur[c], cur[c-1])+grid[r][c];
}
return cur[colSize-1];
}
};
``````

• thank you so much for your explanations!

• @Lihuas_LC whose code (and which one)? Reviewing the OP codes they all fill the data with that single element and return it without going into any loops.

• great solution!!!

• I used this method to get AC, but I wonder whether this method can solve the problem as following:
01 01 01 01
99 99 99 01
99 01 01 01
99 01 99 99
99 01 01 01
Since we only consider min(sum[i - 1][j], sum[i][j - 1]), we cannot turn left in this test case. Can this work?

• @john10334 i also thought of it,so i think the method above is wrong

• JAVA solution 1:

``````public class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] minSum = new int[m][n];
minSum[0][0] = grid[0][0];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(i == 0 && j > 0) minSum[i][j] = minSum[i][j - 1] + grid[i][j];
else if(j == 0 && i > 0) minSum[i][j] =  minSum[i - 1][j] + grid[i][j];
else if(i > 0 && j > 0) minSum[i][j] = Math.min(minSum[i][j - 1], minSum[i - 1][j]) + grid[i][j];
}
}
return minSum[m - 1][n - 1];
}
}
``````

JAVA solution 2:

``````public class Solution {
public int minPathSum(int[][] grid){
int m = grid.length, n = grid[0].length;
int[] minSum = new int[n];
minSum[0] = grid[0][0];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(i == 0 && j > 0) minSum[j] = minSum[j - 1] +grid[i][j];
else if(j == 0 && i > 0) minSum[j] = minSum[j] + grid[i][j];
else if(i > 0 && j > 0) minSum[j] = Math.min(minSum[j], minSum[j - 1]) + grid[i][j];
}
}
return minSum[n - 1];
}
}
``````

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