给定一个列表L，其中两个列表中相邻的项不能同时在子列表S中选取，并且列表L不包含重复值我想用分而治之的方法设计一个算法，输出一个与它的元素之和相等的子表达式。例如，如果L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]，则S = [1, 5, 7, 15, 13]。
我编写的以下代码不起作用，我认为这不是一种分而治之的方法。
def bestsublist(l):
sublist = []
n = len(l)
totalsum = [None] * (n + 1)
totalsum[n] = 0
for i in range(n-1,-1,-1):
totalsum[i] = max(l[i] + totalsum[min(i+2,n)],totalsum[min(i+1,n)])
if l[i] + totalsum[min(i+2,n)] > totalsum[min(i+1,n)]:
sublist.append(l[l[i] + totalsum[min(i+2,n)] - 1])
else:
sublist.append(l[totalsum[min(i+1,n)] - 1])
return sublist
最佳答案
你的解决方案几乎是正确的唯一的问题是如何构建解决方案子列表。
问题是，在遍历完整个列表之前，您会附加到它，所以您还不知道是否要使用该元素。
所以要修复它，只需再次遍历列表并构建子列表下面是它的外观：
....
for i in range(n-1,-1,-1):
totalsum[i] = max(l[i] + totalsum[min(i+2,n)],totalsum[min(i+1,n)])
i = 0
while i < n:
if l[i] + totalsum[min(i+2,n)] > totalsum[min(i+1,n)]:
sublist.append(l[i])
i += 2
else:
i += 1
return sublist
你的解决方案是动态规划，而不是分而治之。