LeetCode: Unique Paths II

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;
};

Join my Email List for more insights, It's Free!😋

← LeetCode: Serialize and Deserial... LeetCode: Add Strings →