Mam trójkąt z dwustu rzędami, w którym muszę znaleźć maksymalną odległość, aby dostać się z góry na dół trójkąta.

   5
  9 8
 5 4 6
9 7 3 4

Najkrótsza odległość wynosiłaby tutaj 5 + 8 + 4 + 3 = 20. Maksymalna odległość wynosiłaby 5 + 9 + 5 + 9 = 28.

Mam dobry pomysł na algorytm, który chcę zaimplementować, ale staram się go przekształcić w kod.

Mój plan to: zacznij od drugiego do ostatniego wiersza, dodaj maksimum możliwych ścieżek z dolnego rzędu i przejdź do góry.

Na przykład powyższy trójkąt zmieni się w:

   28
  23 19
 14 11 10
9 7 3 4

Jest to znacznie bardziej wydajne niż brutalne wymuszanie, ale mam dwa ogólne pytania:

Używając brute-force, jak mam wymienić wszystkie możliwe ścieżki od góry do dołu (mogą się poruszać tylko do sąsiednich punktów)? Próbowałem tego użyć (trójkąt to lista list zawierających trójkąt):

points=list(itertools.product(*triangle))  

ale zawiera wszystkie możliwe kombinacje z każdego wiersza, nie tylko sąsiadujących członków.Project Euler # 18 - jak brutalnie wymusić wszystkie możliwe ścieżki w strukturze drzewa, używając Pythona? To nieco wyjaśnia możliwe podejście, ale chciałbym użyć itertools i innych modułów (tak pythonowych jak to możliwe)

Jak zmierzałbym do iteracji strategii dodawania każdego maksimum z poprzedniego wiersza i iterowania do góry? Wiem, że muszę zaimplementować pętlę zagnieżdżoną:

for x in triangle:
    for i in x:
        i+=? #<-Not sure if this would even increment it

edit:
what I was thinking was:
triangle[y][x] = max([triangle[y+1][x],triangle[y+1][x+1]])