Minimum O(n) space 12 ms DP solution in C++

• I only need two rows or columns of table that depends on which one is shorter to do DP

``````class Solution {
public:
int MlNAux(vector<vector<int>>& grid){
int m=grid.size()-1;
int n=grid[0].size()-1;
vector<vector<int>> c(2);
for(int i=0;i<c.size();i++) {
c[i].resize(grid[0].size());
}
c[1][n]=grid[m][n];
for(int i=n-1;i>=0;i--)
{
c[1][i]=grid[m][i]+c[1][i+1];
}
int x = 2;
for(int i=m-1;i>=0;i--)
{
c[x%2][n]=grid[i][n]+c[(x%2+1)%2][n];
for(int j=n-1;j>=0;j--)
{
if(c[(x%2+1)%2][j]>c[x%2][j+1])
c[x%2][j]=c[x%2][j+1]+grid[i][j];
else
c[x%2][j]=c[(x%2+1)%2][j]+grid[i][j];
}
x++;
}
return c[(x%2+1)%2][0];
}
int NlMAux(vector<vector<int>>& grid){
int m=grid.size()-1;
int n=grid[0].size()-1;
vector<vector<int>> c(grid.size());
for(int i=0;i<c.size();i++) {
c[i].resize(2);
}
c[m][1]=grid[m][n];
for(int i=m-1;i>=0;i--)
c[i][1]=grid[i][n]+c[i+1][1];
int x = 2;
for(int i=n-1;i>=0;i--)
{
c[m][x%2]=grid[m][i]+c[m][(x%2+1)%2];
for(int j=m-1;j>=0;j--)
{
if(c[j][(x%2+1)%2]>c[j+1][x%2])
c[j][x%2]=c[j+1][x%2]+grid[j][i];
else
c[j][x%2]=c[j][(x%2+1)%2]+grid[j][i];
}
x++;
}
return c[0][(x%2+1)%2];
}
int minPathSum(vector<vector<int>>& grid) {
if(grid.size()==0)
return 0;
if(grid[0].size()==0)
return 0;
if(grid.size()==1)
{
int result=0;
for(int i=grid[0].size()-1;i>=0;i--)
result+=grid[0][i];
return result;
}
if(grid[0].size()==1)
{
int result=0;
for(int i=grid.size()-1;i>=0;i--)
result+=grid[i][0];
return result;
}
if(grid.size()>grid[0].size())
return NlMAux(grid);
else
return NlMAux(grid);
}
};
``````

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