Dynamic programming in Python

  • 0
    class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            :type obstacleGrid: List[List[int]]
            :rtype: int
            m = len(obstacleGrid)
            if m==0:    return 0
            n = len(obstacleGrid[0])
            if n==0:    return 0
            # initialize a table with '0's
            table = [[0 for j in range(n)] for i in range(m)]
            for j in range(n):
                if obstacleGrid[0][j] == 1:
                    table[0][j] = 1
            for i in range(m):
                if obstacleGrid[i][0] == 1:
                    table[i][0] = 1
            # dynamic programming
            for i in xrange(1, m):
                for j in xrange(1, n):
                    if obstacleGrid[i][j] == 0:
                        table[i][j] = table[i-1][j] + table[i][j-1]
            return table[m-1][n-1]

Log in to reply

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