DSA - Unique Paths II - C++,Dynamic Programming

Hey, so today we are going to solve Leetcode - Unique Paths II

Problem Link- https://leetcode.com/problems/unique-paths-ii/

class Solution {
public:

      int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

      int m = obstacleGrid.size(); int n = onstacleGrid[0].size(); 
      vector<vector<int>> dp(m, vector<int>(n, 0));
      if(obstacleGrid[0][0] == 1){
      dp[0][0] = 1; 
      }

      for(int i =1; i<m; i++){
      if(dp[i][0] == 0){
        dp[i][0] = dp[i-1][0]; 
        } 
      }

      for(int j =0; j<n; j++){
      if(dp[0][j] == 0) {
         dp[0][j] = dp[0][j-1];
         }
      }

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

      return dp[m-1][n-1];
     }
}

The code defines a Solution class that encapsulates the logic for calculating the number of unique paths in a grid with obstacles. The main method is uniquePathsWithObstacles, which takes the obstacleGrid as input and returns the number of unique paths.

Here's a step-by-step explanation of the code and its visualization:

1. The uniquePathsWithObstacles function initializes the dimensions m and n of the obstacleGrid. It also creates a 2D dynamic programming table dp of size m x n, initialized with zeros.

2. The code checks if the top-left cell (0, 0) is an obstacle (obstacleGrid[0][0] == 1). If not, it sets dp[0][0] to 1, indicating that there is one unique path to reach the top-left cell.

3. The code fills the first column of the dp table. Starting from the second row (index 1), for each cell (i, 0), if it is not an obstacle (obstacleGrid[i][0] == 0), it sets dp[i][0] to the value of the cell above it, dp[i - 1][0]. This indicates that the number of unique paths to reach (i, 0) is the same as the number of unique paths to reach the cell above it.

4. The code fills the first row of the dp table. Starting from the second column (index 1), for each cell (0, j), if it is not an obstacle (obstacleGrid[0][j] == 0), it sets dp[0][j] to the value of the cell to its left, dp[0][j - 1]. This indicates that the number of unique paths to reach (0, j) is the same as the number of unique paths to reach the cell to its left.

5. The code iterates through the remaining cells of the dp table, starting from row 1 and column 1. For each cell (i, j), if it is not an obstacle (obstacleGrid[i][j] == 0), it calculates the number of unique paths to reach that cell by summing the number of unique paths to reach the cell above it (i - 1, j) and the cell to its left (i, j - 1). It assigns this value to dp[i][j].

6. After iterating through all the cells, the value of dp[m - 1][n - 1] represents the number of unique paths to reach the bottom-right cell of the grid.

7. The function returns dp[m - 1][n - 1], which is the number of unique paths in the grid with obstacles.

In summary, the code uses dynamic programming to solve the "Unique Paths II" problem efficiently. It builds a 2D table dp and iteratively fills it by considering each cell's unique paths based on the cells above and to the left. By the end of the process, the bottom-right cell contains the total number of unique paths. This approach avoids redundant calculations and improves the efficiency of the solution.

Note: The code uses a long long data type for the dp table to handle larger grid sizes and avoid integer overflow.