Maximale Wegsumme II

Wenn wir an der Spitze des Dreiecks starten und uns zu angrenzenden Zahlen der Reihe darunter bewegen, ist die maximale Summe von der Spitze zum Boden 23

3
7 4
2 4 6
8 5 9 3

Das ergibt 3 + 7 + 4 + 9 = 23.

Finden Sie die maximale Summe von der Spitze bis zum Boden in triangle.txt (Rechtsklick und 'Link/Ziel speichern unter...'), einer 15K Textdatei, die ein Dreieck mit einhundert Reihen enthält.

HINWEIS: Dies ist eine deutlich schwerere Version von Problem 18. Es ist nicht möglich, jede einzelne Route auszuprobieren, um dieses Problem zu lösen, da es insgesamt 2⁹⁹ Routen gibt! Wenn man eine Billion (10¹²) Routen pro Sekunde berechnen könnte, würde es über 20 Milliarden Jahre dauern, um diese alle zu berechnen. Es gibt einen effizienten Algorithmus, um das Problem zu lösen. ;o)