在数组中寻找最长的几何级数

Question

我正在尝试实现一个动态规划算法，用来找出一个列表中最长的几何级数的长度。我发现了一个算法：http://www.cs.illinois.edu/~jeffe/pubs/pdf/arith.pdf，并试着把它修改成适用于几何级数的。但是，我无法让它正常工作。

我的代码是：

def dp(numbers):
  numbers = sorted(numbers)

  n = len(numbers)
  table = [[2] * n] * n
  for i in range(n):
    table[i][n - 1] = 2

  largest = 2
  for j in range(n - 1, -1, -1):
    i = j - 1
    k = j + 1
    while i >= 0 and k <= n - 1:
      if numbers[j] > math.sqrt(numbers[i] * numbers[k]):
        k += 1
      elif numbers[j] < math.sqrt(numbers[i] * numbers[k]):
        table[i][j] = 2
        i -= 1
      elif numbers[j] == math.sqrt(numbers[i] * numbers[k]):
        table[i][j] = table[j][k] +  1
        largest = max(largest, table[i][j])
        i -= 1
        k += 1

    while i >= 0:
      table[i][j] = 2
      i -= 1

  return largest

举个例子，如果我运行 print dp([1, 2, 4, 8, 16, 32, 64])，我得到的结果是4，但实际上应该是7。对于我哪里出错了，任何帮助都将非常有用。

Answer 1

问题出在这里：

table = [[2] * n] * n

这段代码的意思是创建一个包含一个n元素列表的列表，重复n次。问题在于，这些列表是同一个（用is来判断，而不是用==），而不是它们的副本，所以当你更新其中一个时，其他的也会一起更新，这样就不好了。例如：

>>> lst=[[2]]*2
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
True
>>> lst[0][0]=1
>>> lst
[[1], [1]]

解决办法是写成：

table = [[2] * n for i in range(n)]

这样做会重复运行[2] * n，从而得到n个副本，虽然它们最开始是==相等的，但不是is相等的。

>>> lst=[[2]for i in range(2)]
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
False
>>> lst[0][0]=1
>>> lst
[[1], [2]]

补充说明：另外，for j in range(n - 1, -1, -1):应该改成for j in range(n - 2, -1, -1):，这样才能和伪代码完全一致，不过这并不是导致错误的原因。