24ms O(n)-space DP solution in C++ beats 98.59%


  • 0
    B

    Used some conditions to simplify the cases on border

    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(), n=grid[0].size();
        // directly copy every cell to the dp[][]
        vector<vector<int>> dp=grid;
        
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                // dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] )
                int x = i-1>=0? dp[i-1][j] : INT_MAX;
                int y = j-1>=0? dp[i][j-1] : INT_MAX;
                // this condition is specifically for dp[0][0] 
                if(x==INT_MAX && y==INT_MAX) continue;
                dp[i][j] += min(x, y);
            }
        }
        return dp[m-1][n-1];
    }

Log in to reply
 

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