谁能告诉我为什么这段代码不产生每个递增的子序列? 我使用动态编程来解决这个问题,但我不明白为什么这段代码会失败。 参数 A 是一个整数序列。
def LIS(A):
# make a list of lists
L = list()
for i in range(0, len(A)):
L.append(list())
#the first increasing subsequence is the first element in A
L[0].append(A[0])
for i in range(1, len(A)):
for j in (0, i):
# a new larger increasing subsequence found
if (A[j] < A[i]) and ( len(L[i]) < len(L[j]) ):
L[i] = L[j]
L[i].append(A[i])
# print an increasing subsequence
print L[i]
此算法为 A = [3, 5, 10, 0, 1, 100, 2, 4, 7] 生成的示例输出:
[3, 5]
[3, 5, 10]
[0]
[1]
[3, 5, 10, 100]
[2]
[3, 5, 10, 100, 4]
[3, 5, 10, 100, 4, 7]
None
正确的输出:
[3]
[3, 5]
[3, 5, 10]
[0]
[0, 1]
[3, 5, 10, 100]
[0, 1, 2]
[0, 1, 2, 4]
[0, 1, 2, 4, 7]
请您参考如下方法:
我在你的代码中发现了两个错误
1.你假设列表是不可变的,但它们不在 python 中
L[i] = L[j] this is going to make L[i] point to the same list pointed by L[j]
2.for j in (0, i):
这不会将 j 从 0 迭代到 i-1,而是将 j 从 0 迭代到 i。
这是您的代码的固定版本。
def LIS(A):
# make a list of lists
L = list()
for i in range(0, len(A)):
L.append(list())
# the first increasing subsequence is the first element in A
L[0].append(A[0])
for i in range(1, len(A)):
for j in range(0, i):
# a new larger increasing subsequence found
if (A[j] < A[i]) and (len(L[i]) < len(L[j])):
'throw the previous list'
L[i] = []
'add all elements of L[j] to L[i]'
L[i].extend(L[j])
L[i].append(A[i])
for i in range(len(A)):
# print an increasing subsequence
print (L[i])
A = [3, 5, 10, 0, 1, 100, 2, 4, 7]
LIS(A)
