Unique Paths II - Solution & Explanation

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.

This 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.

Optimized C solution utilizes a single-dimension array to save space, updating path counts as it iterates over each grid row while handling obstacles.

We design a function dfs(i, j) to represent the number of paths from the grid (i, j) to the grid (m - 1, n - 1). Here, m and n are the number of rows and columns of the grid, respectively.

The execution process of the function dfs(i, j) is as follows:

• If i \ge m or j \ge n, or obstacleGrid[i][j] = 1, the number of paths is 0;
• If i = m - 1 and j = n - 1, the number of paths is 1;
• Otherwise, the number of paths is dfs(i + 1, j) + dfs(i, j + 1).

To avoid redundant calculations, we can use memoization.

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.

We can use a dynamic programming approach by defining a 2D array f, where f[i][j] represents the number of paths from the grid (0,0) to the grid (i,j).

We first initialize all values in the first column and the first row of f, then traverse the other rows and columns with two cases:

• If obstacleGrid[i][j] = 1, it means the number of paths is 0, so f[i][j] = 0;
• If obstacleGrid[i][j] = 0, then f[i][j] = f[i - 1][j] + f[i][j - 1].

Finally, return f[m - 1][n - 1].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.