我正在练习一些亚马逊面试编码练习，但我一直坚持这个练习。
简而言之，给定一个列表l和一个整数d，我必须将列表拆分为d个部分，使得每个部分的最大值之和最小，例如，对于l = [10,2,20,5,15,10,1], d = 3，应该返回31，因为最佳选项是[10,2,20,5,15],[10],[1] -> 20+10+1 = 31。
问题链接：问题
我考虑将列表拆分为2，用第一部分和d-1递归调用，并取第二部分的最大值(第二部分将开始有一个元素，我们将在每次迭代中向该部分添加一个元素(。
我做到了，我得到了"；在调用Python对象"时超过了最大递归深度；错误我知道这个问题的解决方案很容易找到，但我想知道为什么这种方法不起作用。
def getmin(l, d):
# base case, if the list has d elements each element will be a sublist
if len(l)==d:
return sum(l)
else:
minn = float("inf")
for i in range(1, len(l)-d+1):
val = getmin(l[0:-i], d-1) + max(l[-i:])
if minn > val:
minn = val
return minn
您的列表l并不是您的书面示例中的2d列表，因此您的算法似乎在保持存储您为到达特定点而进行的切割的结果列表和输入列表时遇到了问题。保留一个单独的列表并将结果累积到其中要容易得多，将l视为只读。更不用说，从性能的角度来看，每次递归调用复制它都很痛苦。
在进一步讨论之前，Python建议永远不要使用l作为变量名。更喜欢L、nums或lst——很难区分1、i和l。我将在帖子的其余部分使用L。
类似于您的暴力解决方案是运行一个从0到len(L)的计数器，并使用递归在每个节点尝试各种可能性。在每个i，我们可以将当前编号L[i]附加到最后一个bucket，或者以L[i]作为第一个元素来启动一个新bucket。一个小的优化是只保持每个桶的最大值，而不是所有元素。
现在您有了一个强力解决方案，您可以使用cache来记忆重复的工作。
from functools import cache
import random
def min_sum_of_max_elems_from_d_cuts(L, d):
assert len(L) >= d
@cache
def find_best_cut(i, cuts):
if len(cuts) == d and i == len(L):
return sum(cuts)
elif len(cuts) > d or i >= len(L):
return float("inf")
best = float("inf")
if cuts: # try extending the current cut by L[i]
new_cuts = cuts[:-1] + (max(cuts[-1], L[i]),)
best = min(best, find_best_cut(i + 1, new_cuts))
# try making a new cut at L[i]
return min(best, find_best_cut(i + 1, cuts + (L[i],)))
return find_best_cut(i=0, cuts=tuple())
if __name__ == "__main__":
tests = [
dict(L=[10,2,20,5,15,10,1], d=3, result=31),
dict(L=[10,2,20,5,15,10,1], d=5, result=43),
dict(L=[5,4,2,4,3,4,5,4], d=4, result=16),
dict(L=[22,12,1,14,17], d=2, result=39),
]
for test in tests:
assert min_sum_of_max_elems_from_d_cuts(test["L"], test["d"]) == test["result"]
L = random.Random(42).choices(range(200), k=25)
assert min_sum_of_max_elems_from_d_cuts(L, d=15) == 1056
我将把优化、自下而上的DP和重现留给读者。它看起来和LeetCode 1335有同样的问题，所以目标约束是1 <= len(L) <= 300、0 <= L[i] <= 1000和1 <= d <= 10，所以它需要比这更多的火力来避免TLE。
对于d=1的简单情况，解决方案只是列表的最大值
def getmin(l, d):
if d == 1:
return max(l)
当d大于1时，解决方案是返回添加到递归调用结果中的列表头或尾部中较小的一个
def getmin(l, d):
if d == 1:
return max(l)
if l[0] < l[-1]:
return l[0] + getmin(l[1:], d-1)
else:
return getmin(l[:-1], d-1) + l[-1]