63. Unique Paths II

Hint

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        // Create a 2D vector dp to store the number of unique paths to each cell

        // Initialize the starting point
        // If the starting point has an obstacle, dp[0][0] is 0, otherwise it is 1

        // Fill the first column
        // If there's an obstacle, all cells below it will have 0 paths

        // Fill the first row
        // If there's an obstacle, all cells to the right of it will have 0 paths

        // Fill the rest of the dp table
        for ()
        {
            for ()
            {
                // If the current cell is not an obstacle
                if ()
                {
                    // The number of paths to the current cell is the sum of paths
                    // from the cell above it and the cell to the left of it
                }
            }
        }
        // Return the number of unique paths to the bottom-right corner
    }
};

Solution

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));

        dp[0][0] = obstacleGrid[0][0] ? 0 : 1;

        for (int i = 1; i < m; ++i)
        {
            dp[i][0] = obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1 ? 1 : 0; 
        }

        for (int j = 1; j < n; ++j)
        {
            dp[0][j] = obstacleGrid[0][j] == 0 && dp[0][j - 1] == 1 ? 1 : 0; 
        }

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                if (obstacleGrid[i][j] == 0)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

• T:
  $O(M\cdot N)$
• S:
  $O(M\cdot N)$