0%

Problème 67

Énoncé:

En commençant en haut du triangle ci-dessous et en se déplaçant aux nombres adjacents à la ligne inférieure, le total maximum de haut en bas est $23$.

3
7 4
2 4 6
8 5 9 3

Effectivement, $3 + 7 + 4 + 9 = 23$.

Trouve la somme maximum de haut en bas dans triangle.txt (clic droit, "Enregistrer le lien sous"), un fichier texte de 15Ko contenant un triangle avec une centaine de lignes.

NOTE: C'est une version bien plus difficile du problème 18. Ce n'est pas possible d'essayer chaque route pour résoudre ce problème, puisqu'il y a $2^{99}$ routes au total! Si tu pouvais essayer $10^{12}$ routes chaque secondes, cela prendrait plus de $20$ milliards d'années pour toutes les essayer. Il y a un algorithme efficace pour résoudre le problème. ;o)

Lien du problème originel