C++ dp solutions (O(m*n) and O(n) space).


  • 3
    C
    // O(m*n) space
    int minPathSum1(vector<vector<int>>& grid) {
        vector<vector<int>> dp = grid;
        int row = dp.size(), col = dp[0].size();
        for (unsigned int i = 1; i < row; i++)
            dp[i][0] += dp[i-1][0];
        for (unsigned int j = 1; j < col;  j++) 
            dp[0][j] += dp[0][j-1];
        for (unsigned int i = 1; i < row; i++) 
            for (unsigned int j = 1; j < col; j++) 
                dp[i][j] += min(dp[i-1][j], dp[i][j-1]);
        return dp[row-1][col-1];
    }
    
    // O(n) space
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size(), col = grid[0].size();
        vector<int> dp = grid[0];
        for (unsigned int j = 1; j < col; j++)
            dp[j] += dp[j-1];
        for (unsigned int i = 1; i < row; i++) {
            dp[0] += grid[i][0];
            for (unsigned int j = 1; j < col; j++)
                dp[j] = grid[i][j] + min(dp[j-1], dp[j]);
        }
        return dp[col-1];
    }

  • 0
    T

    You can reduce the O(m*n) solution to O(1) space, just change dp = grid to &dp = grid ;)
    What do you think about this kind of O(1) solutions in general?


Log in to reply
 

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