Beats 100% with O(n) space


  • 3
    F
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            int m = grid.size();
            int n = grid[0].size();
            vector<int> dp(n);
            
            dp[0] = grid[0][0];
            for (int j = 1; j < n; j++) {   // init
                dp[j] = dp[j-1] + grid[0][j];
            }
            
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dp[j] = (j == 0 ? dp[j] : min(dp[j], dp[j-1])) + grid[i][j];
                }   
            }
            return dp[n-1];
        }
    };
    

    In usual provide O(mn) solution first, then try to optimize it. From dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j], you can see it only depends on previous row and current row value, we waste a lot space if use mn space.

    dp[i][j] is row i, column j;
    dp[i][j-1] is row i, column j-1;
    dp[i-1][j] is row i-1, column j;

    if we just use row to represent dp[i], then it should be

    row[j] = min(row[j-1], row[j]) + grid[i][j];

    why dp[i-1][j] is row[j], because before we set new value for row[j], it saves old value, which is dp[i-1][j].

    So the new transition formula is:

    row[j] = min(row[j-1], row[j]) + grid[i][j];

    still use dp variable to replace row, it is:

    dp[j] = min(dp[j-1], dp[j]) + grid[i][j];

    variable j is from 0 to n, same as before. But the i is not used in two dimension row number, just use iteration number. We need do m-1 iterations, because we don't need do it for first row, which is init value.


  • 0
    G

    If I dont use extra space, I do the dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j] on the existing grid: grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]); I think they are the same, but the run time of your solution is much better. I dont know why. would you please tell me the reason?


Log in to reply
 

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