63. Unique Path II Leetcode Python

浏览数：41 / 时间：2015年06月08日

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.

这题的做法和前面的unique path是一样的，都是用的动态规划。不同之处在于需要判断有没有点为1.

直接上代码：

class Solution:
    # @param obstacleGrid, a list of lists of integers
    # @return an integer
    def uniquePathsWithObstacles(self, obstacleGrid):
        rown=len(obstacleGrid)
        coln=len(obstacleGrid[0])
        dp=[[0 for i in range(coln)] for j in range(rown)]
        if obstacleGrid[0][0]!=1:
            dp[0][0]=1
        for row in range(1,rown):
            if obstacleGrid[row][0]!=1 and dp[row-1][0]==1:
                dp[row][0]=1
            else:
                break
        for col in range(1,coln):
            if obstacleGrid[0][col]!=1 and dp[0][col-1]==1:
                dp[0][col]=1
            else:
                break
        for row in range(1,rown):
            for col in range(1,coln):
                if obstacleGrid[row][col]==1:
                    dp[row][col]=0
                else:
                    dp[row][col]=dp[row-1][col]+dp[row][col-1]
        return dp[rown-1][coln-1]

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

63. Unique Path II Leetcode Python