LC63. Unique Paths II

This time, we have obstacles we can’t access.

[
[0,0,0],
[0,1,0],
[0,0,0]
]

means [1][1] is can not be stepped on.

Find the total number of possible to reach the bottom right.

DP

We use steps to keep the numbers of ways to get to [i][j].

Basebase case

steps[0][0] = 1 – obstacle[0][0]
So if there is an obstacle, steps[0][0] = 0

Base case

The top row and the left column are the base case

Row

For each entry in top row, if it’s equals to the entry to its left if the entry itself is not an obstacle.

Column

in similar fashion

Recurrence

It is very similar, but this time, steps[i][j] will remain zero if there is an obstacle at [i][j]

Corner cases

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        std::vector<std::vector<long long>> steps(m, std::vector<long long>(n, 0));
        // steps[i][j] stores num of ways to get to [i + 1][j + 1]

        steps[0][0] = 1 - obstacleGrid[0][0];
        for (int i = 1; i < m; i++)
            if (obstacleGrid[i][0] != 1)
                steps[i][0] = steps[i -1][0];
        for (int i = 1; i < n; i ++)
            if (obstacleGrid[0][i] != 1)
                steps[0][i] = steps[0][i - 1];
        for (int i = 1; i < m; i ++){
            for (int j = 1; j < n; j ++){
                long long top = (-obstacleGrid[i - 1][j] + 1) * steps[i - 1][j];
                long long left = (1 - obstacleGrid[i][j - 1]) * steps[i][j - 1];
                if (obstacleGrid[i][j] != 1)
                    steps[i][j] = top + left;
            }
        }
        return steps[m - 1][n - 1];
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax