Вопрос-алгоритм: Поиск самого дешевого рейса ⇐ Python

[Anonymous]

Недавно я проходил собеседование в компании (начинающейся с буквы М и заканчивающейся на А), где мне задали этот вопрос. Все еще практикую свои алгоритмы, поэтому надеялся, что кто-нибудь поможет мне понять, как решить эту проблему и подобные проблемы.
Проблема:
Вам даны 2 массива. Например:

Код: Выделить всё

D = [10,7,13,12,4]
R = [5,12,7,10,12]

Код: Выделить всё

D

обозначает цены вылета на рейсы из города А в город Б. R обозначает обратные цены на авиабилеты из города Б в город А. Найдите минимальную стоимость перелета туда и обратно между городами A и городами B. Например, минимум в примере — D[1] + R[2].
(возможен только обратный рейс с тем же или более высоким индексом от вылета полет)
Самая сложная часть заключается в том, что, очевидно, вы должны уйти, прежде чем вернуться.
Наивный подход — это просто двойной цикл for, объединяющий все возможности. Тем не менее, я знаю, что есть лучший подход, но не могу понять его. Я считаю, что мы хотим создать своего рода временный массив с минимальным на данный момент или что-то в этом роде...
Спасибо за чтение.

Подробнее здесь: https://stackoverflow.com/questions/699 ... est-flight