最大化两个整数列表的和?(限制)

Question

最近这是我面试时遇到的一个问题，我不能很快解决。

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

例如，你有两个城市，洛杉矶和纽约，你可以在这两个城市收款。你可以去另一个城市旅行，但要做到这一点，你必须跳过一个条目，你如何最大化你的钱?假设您必须收集资金的天数是<=在纽约和洛杉矶(两个列表)的天数。

下面是两个示例列表:

LA: [300,400,800,900]

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

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

你怎么做才能得到最大的收益?这是我目前所看到的:

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]

我正在尝试创建两个最优收入列表，但这种方式似乎非常违反python。有什么快速而简单的方法来解决这个问题?

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在评论中指出的那样，记忆可以提高性能。