Using dynamic programming, we can track the number of unique paths to each cell in the grid. Initialize a DP matrix of the same dimensions as the grid. If a cell contains an obstacle (value of 1), it will have 0 paths. Start from the top-left corner and accumulate the number of paths by adding the values from the cell above and the cell to the left, if they exist, taking into account obstacles.
Time Complexity: O(m * n), because each cell in the matrix is calculated once.
Space Complexity: O(m * n), for the DP table.
1public class Solution {
2 public int UniquePathsWithObstacles(int[][] obstacleGrid) {
3 int m = obstacleGrid.Length;
4 int n = obstacleGrid[0].Length;
5 int[,] dp = new int[m, n];
6
7 for (int i = 0; i < m; i++) {
8 for (int j = 0; j < n; j++) {
9 if (obstacleGrid[i][j] == 1) {
10 dp[i, j] = 0;
11 } else if (i == 0 && j == 0) {
12 dp[i, j] = 1;
13 } else {
14 dp[i, j] = (i > 0 ? dp[i-1, j] : 0) + (j > 0 ? dp[i, j-1] : 0);
15 }
16 }
17 }
18
19 return dp[m - 1, n - 1];
20 }
21}
22C# implementation reflects the dynamic programming approach to track path counts with consideration for potential obstacles, initiating with base cases.
Instead of using a full 2D DP array, we can optimize space by maintaining just a single row of size `n` to hold the number of paths to positions in the current row. Iterate over the grid, and update path counts by only storing the results for the current row, using the previous row information to calculate paths.
Time Complexity: O(m * n), iterating through the entire grid.
Space Complexity: O(n), only a single row is stored at a time.
1public class Solution {
2 public int UniquePathsWithObstacles(int[][] obstacleGrid) {
3 int m = obstacleGrid.Length;
4 int n = obstacleGrid[0].Length;
5 int[] dp = new int[n];
6 dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
7
8 for (int i = 0; i < m; i++) {
9 for (int j = 0; j < n; j++) {
10 if (obstacleGrid[i][j] == 1) {
11 dp[j] = 0;
12 } else if (j > 0) {
13 dp[j] += dp[j - 1];
14 }
15 }
16 }
17 return dp[n - 1];
18 }
19}
20C# leverages a reduced-space DP approach whereby current row path possibilities are upheld within a singular simplified array, adapting to grid hindrances.