最近我参加了一家公司（以M开头，以A结尾）的面试，他们问了我这个问题。由于我还在练习算法，所以希望有人能帮助我理解如何解决这个问题，以及类似的问题。
问题：
你被给定2个数组，例如：
D = [10,7,13,12,4]
R = [5,12,7,10,12]
D 表示从城市 A 到城市 B 的航班的出发价格。 R 表示从城市 B 到城市 A 的航班的回程价格。找到往返城市 A 和城市 B 之间的最低往返机票费用。例如，本例中的最小值为 D[1] + R[2]。
(只能在同一或更高索引的出发航班上搭乘返程航班)
棘手的部分是显然你必须先出发再返回。
天真的方法是使用双重循环组合所有可能性。但是，我知道有一种更好的方法，但我想不出来。我相信我们要创建某种临时数组以记录目前为止的最小值之类的东西……
谢谢阅读。
我对@user1984的解决方案非常满意。但是如果你真的想要给他们留下深刻印象：
from itertools import accumulate
monoQ = list(accumulate(reversed(R), min))
monoQ.reverse()
best = min(d + r for d, r in zip(D, monoQ))
大多数人都熟悉list（accumulate（（1、2、3、4 5），operator.add）），它返回（1、3、6、10、15），但使用min将使结果是到目前为止所见过的最小元素。 因为你想从这里到结尾取得最小的元素，所以必须反转列表，累加，然后再次反转。
由于这在其他答案的讨论中出现了，因此可以重写为O（1）空间。
best = min(d + r for d, r in zip(reversed(D), accumulate(reversed(R), min)))
这种方法有些取巧，除非明确要求使用O(1)空间的解决方案，否则不建议使用。
不幸的是，您必须使用 reverse(D) 并从列表末尾开始处理，而不能使用 reverse(accumulate(...))，因为无法将 reverse 应用于累加。 zip，reversed 和 accumulate 都返回迭代器而不是列表或元组。
accumulate ：D - user1984R创建一个单调队列/栈，然后您可以在D的长度n的O(n)时间内解决该问题。R = [5, 12, 9, 10, 12] => [5, 9, 9, 10, 12]
如您所见，在每一步中，我们可以访问索引 i 及以上可能的最便宜的返回航班。
现在，迭代D的元素并查看monoQ中的该索引。由于monoQ中该索引是R中对于 i 及以上可能的最小值，因此您现在知道在该点上无法做得更好。
代码示例：
D = [10,7,15,12,4]
R = [5,12,9,10,12]
monoQ = [0]*len(R)
monoQ[-1] = R[-1]
for i in range(len(R)-2, -1, -1):
monoQ[i] = min(monoQ[i+1], R[i])
best = R[0]+D[0]
for i, el in enumerate(D):
best = min(best, D[i]+monoQ[i])
print(best)
D[i]，您可以使用返回的航班R[i]及以上或者R[i+1]及以上？ - user1984