# 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)
dp  = [[0 for i in range(col)] for j in range(row)]

dp = int(obstacleGrid == 0)

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

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  = [ * col] * row


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


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.