python - 最大化两个整数列表之间的总和？ (有限制)

Question

最近这是一个面试问题，我无法快速解决。

如果你有两个列表，你想最大化它们之间的总和，但你一次只能取一个条目，如果想跳转到另一个列表，你必须跳过一个条目，你会怎么做是吗？

例如，您有两个城市，洛杉矶和纽约，您可以在两个城市收款。你可以去另一个城市旅行，但这样做你必须跳过一次入境，你将如何最大化你的钱？假设您必须收款的天数 <= 在纽约和洛杉矶(两个列表)的天数。

这里有两个示例列表:

洛杉矶:[300, 400, 800, 900]

纽约:[829、450、950、300、500、300]

您可以先乘坐 300，然后乘坐 400。或者，您可以乘坐 300，第二天旅行(跳过 400 和 450)，然后在纽约乘坐 950。

您可以选择哪条路来获得最大的 yield ？这是我目前所拥有的:

def maximize(n, la_income, ny_income):
 "Assume n <= len(sf_income), n <= len(ny_income)"
    ny_optimals=defaultdict()
    la_optimals=defaultdict()
    for e in range(0,len(sf_income),-1):
        if la_optimal[e+1]>ny_optimal[e+2]:
            la_optimal[e]=la_income[e]+la_optimal[e+1]
        else:
            la_optimal[e]=la_income[e]+ny_optimal[e+2]

我正在尝试创建两个最佳收入列表，但这种方式似乎非常不符合 pythonic。什么是解决这个问题的快速和 pythonic 方法？

Answer 1

来点递归搜索怎么样？

LA = [300, 400, 800, 900]

NY = [829, 450, 950, 300, 500, 300]

def search(now, nxt):
    if len(nxt) < 2:
        return now
    elif not now:
        return nxt[1:]
    stick = [now[0]] + search(now[1:], nxt[1:])
    switch = search(nxt[1:], now[1:])
    return max((stick, switch), key=sum)

print(search(LA, NY))

正如 roippi 在评论中指出的那样，内存将提高性能。