DP using C++(4ms)


  • 0
    B
    class Solution {
    public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        if(m == 0) return 0;
        int n = obstacleGrid[0].size();
        if(n == 0) return 0;
        
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)  return 0;
        
        int **dp = new int*[m+1];
        for(int i = 0; i <= m; i ++){
            dp[i] = new int[n+1];
        }
        
        for(int i = 0; i <= m; i ++) dp[i][0] = 0;
        for(int j = 0; j <= n; j ++) dp[0][j] = 0;
        
        dp[1][1] = 1;
        for(int i = 2; i <= m; i ++){
            if(obstacleGrid[i-1][0] == 1) dp[i][1] = 0;
            else dp[i][1] = dp[i-1][1];
        }
        
        for(int i = 2; i <= n; i ++){
            if(obstacleGrid[0][i-1] == 1) dp[1][i] = 0;
            else dp[1][i] = dp[1][i-1];
        }
    
        for(int i = 2; i <= m; i ++){
            for(int j = 2; j <= n; j ++){
                if(obstacleGrid[i-1][j-1] == 1) dp[i][j] = 0;
                else{
                    dp[i][j] = (obstacleGrid[i-2][j-1] == 1 ? 0 : dp[i-1][j]) +
                    (obstacleGrid[i-1][j-2] == 1 ? 0 : dp[i][j-1]);
                }
            }
        }
        
        int res = dp[m][n];
        for(int i = 0; i <= m; i ++){
            delete [] dp[i];
        }
        
        delete [] dp;
        
        return res;
    }
    

    };


Log in to reply
 

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