**Introduction:**

Today, we’ll solve **Unique Paths II** (LeetCode #63), which is a variation of the original **Unique Paths** problem. This time, the grid has obstacles that block certain paths, and our goal is to calculate the number of unique paths the robot can take from the top-left corner to the bottom-right corner. We’ll use **Dynamic Programming (DP)** to efficiently solve this problem.

If you’re interested in a video walkthrough of this solution, check out my explanation on YouTube here.

## Problem Overview:

You’re given an `m x n`

grid where:

`0`

represents an open space,`1`

represents an obstacle that the robot cannot pass through.

The robot can only move **right** or **down** at any point. The task is to return the number of unique paths the robot can take to reach the bottom-right corner from the top-left corner, avoiding obstacles.

**Example:**

Input:

`luaCopy code````
obstacleGrid = [[0,0,0],
[0,1,0],
[0,0,0]]
```

Output: `2`

Explanation: The robot can take the following paths:

- Right → Right → Down → Down
- Down → Down → Right → Right

## Solution Approach:

We’ll use **Dynamic Programming (DP)** to solve the problem in an optimal manner.

**Grid Representation**: We’ll represent the number of ways to reach a particular cell in the grid using a DP array. Initially, there is only one way to reach the starting point.**Obstacle Handling**: If a cell contains an obstacle (`1`

), we set its value in the DP array to`0`

, indicating that there are no valid paths through that cell.**Update the DP Array**: For each cell, if there’s no obstacle, we calculate the number of paths to that cell by summing the values of the cell directly above it and the one to the left.

## Code Implementation:

`javaCopy code````
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid[0].length;
int[] dp = new int[n];
dp[0] = 1;
for (int[] row : obstacleGrid) {
for (int j = 0; j < n; j++) {
if (row[j] == 1) {
dp[j] = 0; // No paths through an obstacle
} else if (j > 0) {
dp[j] += dp[j - 1]; // Sum paths from top and left
}
}
}
return dp[n - 1]; // The bottom-right corner has the result
}
}
```

## Explanation of the Code:

**Initial Setup**: We create a DP array`dp[]`

where`dp[j]`

stores the number of ways to reach column`j`

in the current row. Initially,`dp[0] = 1`

, meaning there is one way to start at the top-left corner.**Dynamic Programming Logic**:- For each row in the obstacle grid, we iterate through each cell:
- If the cell is an obstacle (
`1`

), we set`dp[j] = 0`

because the robot cannot pass through it. - If there’s no obstacle and we’re not in the first column (
`j > 0`

), we update`dp[j]`

by adding the value from the cell directly to its left (`dp[j - 1]`

).

- If the cell is an obstacle (

- For each row in the obstacle grid, we iterate through each cell:
**Result**: At the end of the iterations,`dp[n-1]`

contains the number of unique paths to the bottom-right corner.

## Explanation with Example:

Let’s walk through the input:

`javaCopy code````
obstacleGrid = [[0,0,0],
[0,1,0],
[0,0,0]]
```

- We initialize our DP array:
`dp = [1, 0, 0]`

. **First Row**(no obstacles):- After processing,
`dp = [1, 1, 1]`

, meaning there’s 1 way to reach each cell in the first row.

- After processing,
**Second Row**(one obstacle at`grid[1][1]`

):- After processing,
`dp = [1, 0, 1]`

. The obstacle blocks paths to the second cell, so we skip it, but the rightmost cell can still be reached from the left.

- After processing,
**Third Row**(no obstacles):- After processing,
`dp = [1, 1, 2]`

. The rightmost cell can be reached either from above or from the left, resulting in 2 unique paths.

- After processing,

Thus, the result is `2`

.

## Conclusion:

The dynamic programming approach ensures that we efficiently compute the number of unique paths, even with obstacles in the grid. The time complexity is O(m * n), making it very efficient for large grids.

Dynamic Programming is a powerful technique for solving pathfinding problems like this one. For a step-by-step walkthrough, check out my detailed explanation in the YouTube video here.

Feel free to ask questions or leave feedback in the comments. Happy coding!