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


  • 145

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

  • 0
    S

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


  • 2

    Hi, scimagian. You are very welcome :-)


  • 0
    D
    This post is deleted!

  • 1
    T

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


  • 0

    The process of optimization is excellent!


  • 0
    N

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


  • 0
    T

    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.


  • 1
    A

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

  • 0
    C

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

  • 0
    R

    excellent ,amazing , thanks for share .


  • 0

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


  • 0

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

  • 0

    thank you so much for your explanations!


  • 0
    L

    wrong answer for [[1]]


  • 0
    T

    @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.


  • 0
    P

    great solution!!!


  • 0
    J

    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?


  • 0
    H

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


  • 0
    J

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

Log in to reply
 

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