Максимальный путь треугольника (Python)
У меня есть треугольник с двумя сотнями рядов, где я должен найти максимальное расстояние, чтобы пройти от верха до низа треугольника.
5
9 8
5 4 6
9 7 3 4
Здесь кратчайшее расстояние будет 5 + 8 + 4 + 3 = 20. Максимальное расстояние будет 5 + 9 + 5 + 9 = 28.
У меня есть хорошая идея об алгоритме, который я хочу реализовать, но я изо всех сил пытаюсь превратить его в код.
Мой план таков: начните со 2-й до последней строки, добавьте максимум возможных путей из нижней строки и выполните итерации до верхней части.
Например, приведенный выше треугольник превратится в:
28
23 19
14 11 10
9 7 3 4
Это гораздо более эффективно, чем грубое принуждение, но у меня есть два общих вопроса:
Используя грубую силу, как мне перечислить все возможные пути сверху вниз (можно перемещаться только в соседние точки)? Я попытался использовать это (треугольник это список списков, содержащих треугольник):
points=list(itertools.product(*triangle))
но он содержит все возможные комбинации из каждого ряда, а не только смежные элементы.Project Euler # 18 - как перебрать все возможные пути в древовидной структуре с помощью Python? Это несколько объясняет возможный подход, но яя хотел бы использовать itertools и любые другие модули (как можно более pythonic)
Как бы я повторил стратегию добавления каждого максимума из предыдущего ряда и итерации к вершине? Я знаю, что я должен реализовать вложенный цикл:
for x in triangle:
for i in x:
i+=? #