Coder's Cat

LeetCode: Unique Paths II

2020-07-30

Solution for LeetCode: Unique Path II, Depth-first-search algorithm with memorization.

file:img/2020_07_30_unique-path-ii.org_20200730_182156.png

Solution: DFS with memorization

Note: we can only move with the direction of right or down. y), the way to (x, y) = (x-1, y) + (x, y-1), under the condition of [x-1, y] or [x, y-1] is not obstacle grid.

So we could use a DFS to calculate the number of paths, memorization will reduce much of duplicated computation.

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
ans = 0;
row = obstacleGrid.size();
if(row == 0) return 0;
col = obstacleGrid[0].size();
dp = vector<vector<int>>(row, vector<int>(col, -1));
if(obstacleGrid[0][0] == 1 || obstacleGrid[row-1][col-1] == 1) return 0;
return dfs(obstacleGrid, row-1, col-1);
}

int dfs(vector<vector<int>>& obstacleGrid, int x, int y) {
if(dp[x][y] != -1) return dp[x][y];
if(x == 0 && y == 0) return 1;
int cnt = 0;
if(y-1 >= 0 && obstacleGrid[x][y-1] != 1) // if down is possible
cnt += dfs(obstacleGrid, x, y-1);
if(x-1 >= 0 && obstacleGrid[x-1][y] != 1) // if right is possible
cnt += dfs(obstacleGrid, x-1, y);
dp[x][y] = cnt;
return cnt;
}

int ans;
int row;
int col;
vector<vector<int>> dp;
};