我最近在一家公司接受了一次面试(以M开头，以a结尾(，该公司问了我这个问题。我还在练习我的算法，所以我希望有人能帮助我理解如何解决这个问题，以及这些类型的问题。
问题：
您将获得2个数组。例如：
D = [10,7,13,12,4]
R = [5,12,7,10,12]
CCD_ 1表示从城市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))
大多数人都熟悉返回D0的list(accumulate((1, 2, 3, 4 5), operator.add))，但使用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都返回迭代器，而不是列表或元组。
从返回价格数组R中创建一个单队列/堆栈，然后可以在O(n)中求解，其中n是D的长度。
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)