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) {
            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++)
            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.