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.
1#include <stdio.h>
2
3int uniquePathsWithObstacles(int** obstacleGrid, int m, int n) {
4 int dp[m][n];
5
6 // Initialize DP table
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 if (i == 0) {
14 dp[i][j] = dp[i][j - 1];
15 } else if (j == 0) {
16 dp[i][j] = dp[i - 1][j];
17 } else {
18 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
19 }
20 }
21 }
22 return dp[m - 1][n - 1];
23}
24This solution implements a dynamic programming strategy to fill a DP table. Each cell in the DP table represents the number of unique paths to that cell, calculated by summing the possible paths from the left and above cells, unless they contain obstacles.
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.
1#include <stdio.h>
2
3int uniquePathsWithObstacles(int** obstacleGrid, int m, int n) {
4 int dp[n];
5 memset(dp, 0, sizeof(dp));
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}
19Optimized C solution utilizes a single-dimension array to save space, updating path counts as it iterates over each grid row while handling obstacles.