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

Question

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

Comments

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.

---

OK,it's fine now.

Answer 1

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

Answer 2

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