Максимальный путь треугольника (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+=? #

Ответы на вопрос(2)

Ваш ответ на вопрос