python - 在迷宫中寻找障碍物的路径数

我一直在研究leetcode问题，它实际上是在给定矩阵的情况下，找出迷宫中有效路径的数目。如果obstacleGrid，则在（i，j）处有一个障碍物，否则为零，这是一个有效点我们只能向下和向右移动，目标是从左上角到右下角。
我写了下面的代码：

def uniquePathsWithObstacles(self, obstacleGrid):
    # obstruction at the start
    if (obstacleGrid[0][0] == 1): return 0
    # obstruction at the end
    if (obstacleGrid[-1][-1] == 1): return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    memo = [[0] * n] * m
    # starting move
    memo[0][0] = 1
    # now check the first row
    for j in range(1, n):
        memo[0][j] = 1 if (obstacleGrid[0][j] == 0 and memo[0][j-1] != 0) else 0
    # now check the first column
    for i in range(1, m):
        memo[i][0] = 1 if (obstacleGrid[i][0] == 0 and memo[i-1][0] != 0) else 0
    # now check everything else
    for i in range(1, m):
        for j in range(1, n):
            if (obstacleGrid[i][j] == 1): memo[i][j] = 0
            else: memo[i][j] = memo[i-1][j] + memo[i][j-1]
    return memo[-1][-1]

我采用了明显的DP方法，我知道这个想法是有效的，但是代码有问题；出于某种原因，我认为我的obstacleGrid[i][j] == 1矩阵没有被正确地更新我觉得问题就在眼前，但不知为什么我看不见。感谢任何帮助！
编辑：对于memo，如果在return语句之前有一个obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]，则得到print(memo)。这恰好给了我正确的答案，但是[[1, 1, 2], [1, 1, 2], [1, 1, 2]]矩阵是错误的！

最佳答案

一个问题在于memo = [[0] * n] * m行。
这不会真正创建同一列表的m副本，而是只创建一次[0] * n列表，然后创建memo作为对该列表的m引用列表。对这些列表的任何更改都将修改所有其他列表！
你可以自己试试：

memo = [[0] * 3] * 4
memo[0][1] = 1
print(memo)

这将产生[[0, 1, 0], [0, 1, 0], [0, 1, 0], [0, 1, 0]]。
相反，您必须自己初始化每个列表，例如。，

memo = []
for i in range(m):
  memo.append([0] * n)

关于python - 在迷宫中寻找障碍物的路径数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54973805/