C++ simple dp solution, explained with comments


  • 2
    R
     int minPathSum(vector<vector<int>>& grid) {
            int row=grid.size();  
            if(row==0)return 0;   // if grid contains no element return 0
            int col=grid[0].size(); 
            
            for(int i=0;i<row;i++){   
                for(int j=0;j<col;j++){
                     // for 0'th row top is 0. and for 0'th column left is 0                                   
                    int top = (i==0) ? 0 : grid[i-1][j];
                    int left = (j==0) ? 0 : grid[i][j-1];
                    // if we are at 0'th row then top=0 and left is left element(for grid[0][0] top=0 and left=0)
                    // if we are at 0'th column then left=0 and top is top element (for grid[0][0] top=0 and left=0)
                    if(i==0 || j==0) grid[i][j] += (top==0?left:top);
                   // for every row, column other than 0'th row or 0'th column we just need to add the minimum value
                    //in the current element either it is coming from left or from top
                    else grid[i][j]+=min(top,left);  
                }
            }
            // at the end grid[row-1][col-1] will contain the sum of path which has minimum sum.  
            return grid[row-1][col-1];
        }

Log in to reply
 

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