Unique Paths II

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

---

This is basically the same solution as the first Unique Paths with only a couple of exceptions.  Let's think about just how the robot would get to the final cell in general.  

If we only had one row, then the robot would just go to the right.  If we only had one column, then the robot would just go down.  That tells us that for each cell that the robot has traveled to, the robot must have gotten there from the cell above it or to the left of it.  

To calculate this, we can perform tabulation in the form of bottom-up Dynamic Programming.

We will traverse the grid, and each time we arrive at a new cell, we will track the unique paths to get to that cell by incrementing the cell by the paths from the cell directly above it and the cell directly to the left of it as long as the current cell is not already one, in which case we will mark it zero because there is no way we could go to or from it.

---

Let's start by taking the count of the length and the width, m, and n so that we don't have to keep calculating these lengths later on.

        m, n = len(obstacleGrid), len(obstacleGrid[0])
 

Then, we will create our dp cache which will be a grid where we will keep the running sum of the number of ways to get to each index.

        dp = [[0] * n for row in range(m)]

 

The code above translates to "dp is an array of zeros in the length of n, and we'll have m rows of that array."

 

If the starting point is an obstacle, then there would be no way for us to reach the finish line.

In this case, we will return zero paths.

        if obstacleGrid[0][0] == 1:
            return 0

 

Now, we will handle our base cases of how many ways there are to get to the first row and the first column.

In both of these cases, if there is an obstacle then we can't move any further so we will count the paths to that cell as zero and break.  Otherwise, the cell will be marked as one, because there was only one way for us to get there, from the previous cell.

        for i in range(n):
            if obstacleGrid[0][i] == 1:
                dp[0][i] = 0
                break
            else:
                dp[0][i] = 1

 

        for i in range(m):
            if obstacleGrid[i][0] == 1:
                dp[i][0] = 0
                break
            else:
                dp[i][0] = 1

 

Next, we will traverse the columns and rows from index one because our base cases took care of the first row and column.

        for row in range(1,m):
            for col in range(1,n):

 

If we encounter a cell that is one, then that means we have a giant obstacle in the way and can't move past it.  The number of paths to and from that cell will be zero because we can't get to it and can't move from it.

                if obstacleGrid[row][col] == 1:
                    dp[row][col] = 0

 

Otherwise, for each cell index, we will increment its unique paths element by the number of unique paths in the cell directly above it, and the cell directly to the left.

                else:
                    dp[row][col] = dp[row-1][col] + dp[row][col-1]

 

Once we have filled up our cache with subproblems, the super-problem answer will be in the final index of the cache.

        return dp[-1][-1]

---