Unique Paths II - Optimized [C++]
IntuitionTo navigate through a grid with obstacles, we can utilize dynamic programming to calculate the number of unique paths to each cell while respecting the
# Intuition
To navigate through a grid with obstacles, we can utilize dynamic programming to calculate the number of unique paths to each cell while respecting the obstacles. If a cell contains an obstacle, no path can pass through it, so its value is set to 0. For other cells, the number of paths reaching it is the sum of the paths from the cell above and the cell to the left.

# Approach
1. **Initialization**:
   - Use a 1D DP array (`dp`) to store the number of unique paths to each column in the current row.
   - Initialize `dp[0]` to 1 if the starting cell is not an obstacle, otherwise 0.

2. **Dynamic Programming Transition**:
   - Iterate through the grid row by row.
   - For each cell, check if it contains an obstacle:
     - If it does, set `dp[j]` to 0.
     - Otherwise, update `dp[j]` as `dp[j] + dp[j-1]` (paths from the left).

3. **Edge Cases**:
   - If the grid's start or end cell is an obstacle, the result is 0 as no path can exist.

4. **Final Output**:
   - The value of `dp[n-1]` at the end of the iteration contains the total unique paths to the bottom-right corner of the grid.

# Complexity
- **Time Complexity**: 
  - $$O(m \cdot n)$$, where `m` is the number of rows and `n` is the number of columns, as we process each cell exactly once.

- **Space Complexity**: 
  - $$O(n)$$, as we use a single array of size `n` for dynamic programming.

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

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

        return dp[n - 1];
    }
};

['C++']