Dynamic programming in Python


  • 0
    H
    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:
                    break
                else:
                    table[0][j] = 1
            for i in range(m):
                if obstacleGrid[i][0] == 1:
                    break
                else:
                    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.