# 065 unique paths ii

###65.Unique Paths II

tag : DP

BASE CASE（ i = 0 , j = 0）:
//第一排和第一列，如果没有obstacle， 则走法为1， 一旦有了obstacle，则之后的格子走法都为0

//一旦有obstacle，则dp为0
dp(i, j) = dp（i,j-1) + dp(i-1,j)



Python代码

class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
row = len(obstacleGrid)
col = len(obstacleGrid[0])
dp  = [[0 for i in range(col)] for j in range(row)]

dp[0][0] = int(obstacleGrid[0][0] == 0)

#first row
for j in range(1,col):
if obstacleGrid[0][j] == 1:
dp[0][j] = 0
else:
dp[0][j] = dp[0][j-1]
#first col
for i in range(1,row):
if obstacleGrid[i][0] == 1:
dp[i][0] = 0
else:
dp[i][0] = dp[i-1][0]

for i in range(1,row):
for j in range(1,col):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[row-1][col-1]



dp  = [[0] * col] * row


>>> x = [[]] * 3
>>> x[1].append(0)
>>> x
[[0], [0], [0]]


The problem is that they're all the same exact list in memory. When you use the [x]*n syntax, what you get is a list of n many x objects, but they're all references to the same object. They're not distinct instances, rather, just n references to the same instance.

apachecn/AiLearning