Python实现动态规划时，[None for i in range(len(B))]和[None]*len(B)得出不同结果

Question

def lcs_memo(x, y, i, j, c):
    if i < 0 or j < 0:
        return 0
    if c[i][j] is None:
        if x[i] == y[j]:
            c[i][j] = lcs_memo(x, y, i - 1, j - 1, c) + 1
        else:
            c[i][j] = max(lcs_memo(x, y, i - 1, j, c), lcs_memo(x, y, i, j - 1, c))
    return c[i][j]

基本的实现代码就是这样，x,y代表原字符串，i,j代表相对位置，c代表临时的存储矩阵。
此时，下面的代码输出了正确的值：3

A = 'abccc'
B = 'cccba'
C = [[None for j in range(len(B))] for i in range(len(A))]
print(lcs_memo(A, B, len(A) - 1, len(B) - 1, C))

但是，下面的代码输出了错误的值：1

A = 'abccc'
B = 'cccba'
C = [[None] * len(B)] * len(A)
print(lcs_memo(A, B, len(A) - 1, len(B) - 1, C))

也就是说，下面这两行代码对结果有区别：

C = [[None for j in range(len(B))] for i in range(len(A))]
C = [[None] * len(B)] * len(A)

想了好久也不知道为什么，希望能得到解答。

Answer 1

初始化多维列表最好使用列表推导式。

l = [[]] * 5
print([id(x) for x in l]) # [2337055020296, 2337055020296, 2337055020296, 2337055020296, 2337055020296]

中列表的每一个元素是对初始的[None]的一个引用，其实都是同一个对象。

l = [[] for x in range(5)]
print([id(x) for x in l]) # [2337054512712, 2337055068872, 2337055068360, 2337055020168, 2337055019528]

中每一个元素都是列表推导式计算出来的全新的[None]，是不同的对象。

Answer 2

请先看以下2段代码

>>> b = [[0,0]] * 3
>>> b[0][0] = 4
>>> b
[[4, 0], [4, 0], [4, 0]]

>>> c = [[0, 0] for i in range(3)]
>>> c[0][0] = 4
>>> c
[[4, 0], [0, 0], [0, 0]]

也就是说，使用推导式时，每个位置都生成了新的列表对象，
而使用 乘号时，仅仅是复制了引用，每个位置的元素都只是原来的列表对象的引用，改一个，其他地方也被改了，因而出现你问题中的现象。

如果仅是基本数据类型，就不会出现问题。列表属于容器，保存的是引用。

>>> e = [0] * 3
>>> e[0] = 4
>>> e
[4, 0, 0]

更多推导式的使用可以参考 Python推导式