63. Unique Paths II

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/unique-paths-ii/
• topics: 2D Array, Dynamic Programming

Description

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

Idea

• Dynamic Programming

Code

class Solution:
    def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        if grid[0][0] == 1:
            return 0
 
        grid[0][0] = 1 
        for i in range(0, rows):
            for j in range(0, cols):
                if not i == j == 0:
                    if grid[i][j] == 1:
                        grid[i][j] = 0
                    else:
                        if i > 0:
                            grid[i][j] += grid[i-1][j]
                        if j > 0:
                            grid[i][j] += grid[i][j-1]
        
        return grid[-1][-1]