Unique Path II

Problem

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.

Thoughts

加一个判断条件，类似1

Solution

class Solution:
    """
    @param obstacleGrid: An list of lists of integers
    @return: An integer
    """
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        f = [[0 for i in range(n)] for j in range(m)]
        f[0][0] = 1

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    f[i][j] = 0
                else:
                    if i == 0 and j == 0:
                        continue
                    elif i == 0:
                        f[i][j] = f[i][j-1]
                    elif j == 0:
                        f[i][j] = f[i-1][0]
                    else:
                        f[i][j] = f[i-1][j] + f[i][j-1]

        return f[m-1][n-1]