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


  • 0
    H

    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);
        }
    };
    

Log in to reply
 

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