Python solution with detailed explanation


  • 0
    G

    Solution

    Unique Paths II https://leetcode.com/problems/unique-paths-ii/?tab=Description

    Memoization

    from collections import defaultdict
    class Solution(object):
        def helper(self, i, j, M, N, grid, cache):
            if 0<=i<=M-1 and 0<=j<=N-1 and grid[i][j] != 1:
                if i == M-1 and j == N-1:
                    return 1
                elif i in cache and j in cache[i]:
                    return cache[i][j]
                else:
                    cache[i][j] = self.helper(i+1,j, M, N, grid, cache) + self.helper(i,j+1, M, N, grid, cache)
                    return cache[i][j]
            return 0
        
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            cache = defaultdict(dict)
            M, N = len(obstacleGrid), len(obstacleGrid[0])
            return self.helper(0, 0, M, N, obstacleGrid, cache)
    

    Dynamic Programming

    class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            MM = obstacleGrid
            N = len(MM)
            M = len(MM[0])
            if M == 0:
                return 1
            dp = [0]*M
            dp[0] = abs(MM[0][0]-1)
            for j in range(1, M):
                dp[j] = dp[j-1]*abs(MM[0][j]-1)
            for i in range(1, N):
                temp = [0]*M
                temp[0] = dp[0]*abs(MM[i][0]-1)
                for j in range(1, M):
                    temp[j] = dp[j]*abs(MM[i][j]-1) + temp[j-1]*abs(MM[i][j]-1)
                dp = temp
            return dp[M-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.