Table of contents
No headings in the article.
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:
The
uniquePathsWithObstacles
function initializes the dimensionsm
andn
of theobstacleGrid
. It also creates a 2D dynamic programming tabledp
of sizem x n
, initialized with zeros.The code checks if the top-left cell
(0, 0)
is an obstacle (obstacleGrid[0][0] == 1
). If not, it setsdp[0][0]
to 1, indicating that there is one unique path to reach the top-left cell.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 setsdp[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.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 setsdp[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.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 todp[i][j]
.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.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.