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

shengwubin
  • 227
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)

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

回复
阅读 7.6k
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推导式

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

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],是不同的对象。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏