8 lines C++ DP


  • 0

    There are only 2 directions to reach a given cell [i][j], either from above it or from left,
    dp[i][j-1] (path from its left)
    dp[i-1][j] (path from its above)
    so the min path is the min-sum from 2 directions plus itself: min{dp[i][j-1],dp[i-1][j]}+grid[i][j];

        int minPathSum(vector<vector<int>>& grid) {
            //dp[i][j]=min{dp[i][j-1],dp[i-1][j]}+grid[i][j];
            vector<vector<int>>dp(grid.size(),vector<int>(grid[0].size()));
            dp[0][0]=grid[0][0];
            for(int i=1;i<grid.size();i++) dp[i][0]=grid[i][0]+dp[i-1][0];
            for(int i=1;i<grid[0].size();i++) dp[0][i]=grid[0][i]+dp[0][i-1];
            for(int i=1;i<grid.size();i++)
                for(int j=1;j<grid[0].size();j++)
                    dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            return dp[grid.size()-1][grid[0].size()-1];
        }
    

Log in to reply
 

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