kazi1@的部落格

class Solution(object):
    def walkPaths(self, m, n, x, y, dp):
        if x == m-1 and y == n-1:
            return 1
        if x >= m or y >= n:
            return 0
        if dp[x][y] >= 0:
            return dp[x][y]
        dp[x+1][y] = self.walkPaths(m, n, x+1, y, dp)
        dp[x][y+1] = self.walkPaths(m, n, x, y+1, dp)
        return dp[x+1][y] + dp[x][y+1]

    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[-1 for x in xrange(n+1)] for x in xrange(m+1)]
        return self.walkPaths(m, n, 0, 0, dp)

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0 for x in xrange(n+1)] for x in xrange(m+1)]
        dp[m][n-1] = 1
        for x in xrange(m-1, -1, -1):
            for y in xrange(n-1, -1, -1):
                dp[x][y] = dp[x+1][y] + dp[x][y+1]
        return dp[0][0]

63. Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        yrow = len(obstacleGrid)
        xcol = len(obstacleGrid[0])
        dp = [[0 for x in xrange(xcol+1)] for x in xrange(yrow+1)]
        dp[yrow-1][xcol] = 1
        for x in xrange(xcol-1,-1,-1):
            for y in xrange(yrow-1,-1,-1):
                if obstacleGrid[y][x] == 0:
                    dp[y][x] = dp[y+1][x] + dp[y][x+1]
        return dp[0][0]