C++ DP Solution


  • 0
    S
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            int r = grid.size();
            if(r == 0)
                return 0;
            int c = grid.front().size();
            
            int **dp = new int*[r];
            for(int i=0; i<r; i++)
                dp[i] = new int[c];
    
            //Init the left dp
            dp[0][0] = grid[0][0];
            for(int i=1; i<r; i++) {
                dp[i][0] = grid[i][0] + dp[i - 1][0];
            }
    
            //Init the upper dp
            for(int j=1; j<c; j++)
                dp[0][j] = grid[0][j] + dp[0][j-1];
    
            for(int i=1; i<r; i++) {
                for(int j=1; j<c; j++)
                    dp[i][j] = grid[i][j] + (dp[i-1][j] > dp[i][j-1] ? dp[i][j-1] : dp[i-1][j]);
            }
            return dp[r-1][c-1];
        }
    };
    

Log in to reply
 

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