Minimum Path Sum ---------How can I reduce the memory.


  • 12
    J

    Here is the idea:

    1. f[m][n] is a matrix store the min value of every location we can
      get.
    2. f[0][0] =grid[0][0], f[i][0]=f[i-1][0]+grid[i][0],
      f[0][j]=f[0][j-1]+grid[0][j]
    3. f[i][j]=min(f[i-1][j],f[i][j-1])+grid[i][j].
    4. at last return the f[m-1][n-1]

    class Solution {
            public:
                int minPathSum(vector<vector<int> > &grid) {
                    // IMPORTANT: Please reset any member data you declared, as
                    // the same Solution instance will be reused for each test case.
                    int m=grid.size();
                    int n=grid[0].size();
                    int** f;
                    f=new int*[m];
                    for(int i=0;i<m;i){
                        f[i]=new int[n];
                    }
                    f[0][0]=grid[0][0];
                    for(int i=1;i<m;i++){
                        f[i][0]=f[i-1][0]+grid[i][0];
                    }
                    for(int i=1;i<n;i++){
                        f[0][i]=f[0][i-1]+grid[0][i];
                    }
                    for(int i=1;i<m;i++){
                        for(int j=1;j<n;j++)
                            f[i][j]=min(f[i-1][j],f[i][j-1])+grid[i][j];
                    }
                    return f[m-1][n-1];
                }
                int min(int a,int b){
                    if(a>b)
                        return b;
                    else
                        return a;
                }
            };

  • 0

    Welcome Joey! Please format your code properly by selecting your code, and clicking on the {} button. Also please read the FAQ for tips on asking a question.


  • 0
    J

    OK,it's fine now.


  • 41

    Given the dynamic programming formula f[i][j]=min(f[i-1][j],f[i][j-1])+grid[i][j]:

    Assume that you are populating the table row by row, the current value (f[i][j]) will be used immediately in the calculation of f[i][j+1], so there is no need to store all the previous column values.

    Therefore, you can do it in linear space complexity. Below is a sample code courtesy of Linfuzki@.

    class Solution {
    public:
        int minPathSum(vector<vector<int> > &grid) {
            if (grid.empty() || grid[0].empty()) return 0;
            int m = grid.size(), n = grid[0].size();
    
            vector<int> dp(n + 1, INT_MAX);
            dp[1] = 0;
    
            for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j)
                    dp[j + 1] = min(dp[j + 1], dp[j]) + grid[i][j];
    
            return dp.back();
        }
    };

  • 0
    U

    You can reduce memory to O(n), if you visited i & i - 1 by i % 2, (i + 1) % 2


  • 8
    G

    Just do it in place.

    class Solution:
        # @param grid, a list of lists of integers
        # @return an integer
        def minPathSum(self, grid):
            m = len(grid)
            n = len(grid[0])
            for i in range(m):
                for j in range(n):
                    if i == j == 0:
                        pass
                    elif i == 0:
                        grid[i][j] += grid[i][j-1]
                    elif j == 0:
                        grid[i][j] += grid[i-1][j]
                    else:
                        grid[i][j] += min(grid[i-1][j], grid[i][j-1])
            return grid[-1][-1]

  • 0
    U

    The space can be O(mn), O(m), O(n) or O(min(m, n)) depending on how you do the DP. The last is achieved by progress anti-diagonally.


  • 0
    J

    Here is a O(n) solution:

    class Solution {
        public:
            int minPathSum(vector<vector<int> > &grid) {
                map<int,int> result;
                //DP
                for(int j =0 ; j < grid.back().size(); j ++)
                {
                    result[j] = INT_MAX;
                }
                result[-1]=0;
                for(int i = 0 ; i < grid.size() ; i ++)
                {
                    for(int j =0 ; j < grid.back().size(); j ++)
                    {
                            if(result[j] < result[j-1])
                            {
                                result[j]+= grid[i][j];
                            }
                            else
                            {
                                result[j]= result[j-1]+grid[i][j];
                            }
                            result[-1]= INT_MAX;
                    }
                }
                return result[grid.back().size()-1];
            }
        };

  • 0
    B

    Hi! Thank you for your neat code! Could you explain it?


  • 1
    R

    This is a java version of answer. The initial value assignment is key point.

    public class Solution {
        public int minPathSum(int[][] grid) {
        //Deal with boundary condition
            if (grid.length==0||grid[0].length==0) return 0;
            //Declare
            int row=0;
            int column=0;
            int sum[]=new int[grid[0].length+1];
            //Initiate values
            for(column=0;column<=grid[0].length;column++)
                sum[column]=Integer.MAX_VALUE;
            //Cycle
            sum[1]=0;
            for (row=0;row<grid.length;row++)
                for (column=0;column<grid[0].length;column++)
                    sum[column+1]=Math.min(sum[column+1],sum[column])+grid[row][column];
                	
            
        return sum[column];
        }
    }

  • 0
    W

    Hi, 1337c0d3r, What do you think that we just use the in-place-calculation algorithm written below by geekan? In that way, we do not need any extra space.


  • 2
    W

    actually,we can do it in place by triping through the grid only once.in order to reduce the code,i specially handle the first row and the first column.This is a c++ version of answer.

    class Solution {
    public:
    	
        int minPathSum(vector<vector<int> > &grid) {
            
    		int row,col,rowNum=grid.size(),colNum=grid[0].size();
    		for(col=1;col<colNum;++col)
    			grid[0][col]+=grid[0][col-1];
    		for(row=1;row<rowNum;++row)
    			grid[row][0]+=grid[row-1][0];
    		for(row=1;row<rowNum;++row)
    			for(col=1;col<colNum;++col)
    				grid[row][col]+=grid[row-1][col]>grid[row][col-1]?grid[row][col-1]:grid[row-1][col];
    		return grid[rowNum-1][colNum-1];
        }
    };
    

  • 2
    L

    pretty straight forward DP problem

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

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    L

    nice solution, row by row is keywords, just calculate it in mind, and will get the answer, nice work. thanks.


  • 0
    Q
    This post is deleted!

  • 0
    P

    Its not the most efficient one. You can still reduce space complexity to O(n).


  • 0
    P

    That was a badass answer 1337c0d3r !


Log in to reply
 

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