Simple Python DP beats 99.48%


  • 0
    L

    Not sure if it is because they upgrade the machines. As I did not see any Python solution posted, I will just share mine.

    def uniquepath(r, c, grid, cache):
        if r == len(grid) or c == len(grid[0]):
            return 0
        if cache[r][c] != -1:
            return cache[r][c]
        cache[r][c] = up(r+1,c,grid,cache) + up(r,c+1,grid,cache)
        return cache[r][c]
    
    class Solution(object):
        def uniquePathsWithObstacles(self, grid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            if grid[-1][-1] == 1:
                return 0
            cache = [[0 if grid[r][c] == 1 else -1 for c in xrange(len(grid[r]))] for r in xrange(len(grid))]
            cache[-1][-1] = 1
            return uniquepath(0, 0, grid, cache)
    

Log in to reply
 

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