DP bitwise operation


  • 0
    H

    4ms DP solution. Use bitwise operation here.

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    
        int rows = obstacleGrid.size();
        int cols = obstacleGrid.front().size();
        obstacleGrid[0][0] = (~obstacleGrid[0][0]) & 1;
        for (int col=1; col<cols; ++col)
        {
            obstacleGrid[0][col] = (obstacleGrid[0][col] - 1) & obstacleGrid[0][col-1];
        }
        
        for (int row=1; row<rows; ++row)
        {
            obstacleGrid[row][0] = (obstacleGrid[row][0] - 1) & obstacleGrid[row-1][0];
        }
        
        for (int row=1; row<rows; ++row)
        {
            for (int col=1; col<cols; ++col)
            {
                obstacleGrid[row][col] = (obstacleGrid[row][col] - 1) & (obstacleGrid[row-1][col] + obstacleGrid[row][col-1]);
            }
        }
        return obstacleGrid[rows-1][cols-1];
    }

Log in to reply
 

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