Een rij positieve getallen wordt in een driehoek geplaatst, zoals getoond in bijgaande figuur.

Beschouw een pad dat start in de bovenste top van de driehoek, en dat via adjacente getallen, een getal per niveau, naar een getal in de basis van de driehoek gaat. De getallen in dit pad worden gesommeerd. Gevraagd is de grootst mogelijke som te bepalen die zo kan worden bekomen.

Anders verwoord, gegeven deze gerichte graaf, bepaal een pad van wortel naar blad waarbij de som van de toppen maximaal is:

Een optimaal pad is in het rood aangeduid.

Ontwerp en implementeer een algoritme met dynamisch programmeren voor dit probleem.

Opgave

Schrijf een Python-functie maximum_descent(driehoek: list) die een driehoekige matrix binnenkrijgt, en de maximale pad van wortel naar blad te bepalen met behulp van dynamisch programmeren. Deze functie moet enkel het maximale gewicht teruggeven. De driehoek bevat enkel positieve gehele getallen

Voorbeelden

>>> maximum_descent([[2], [5, 4], [3, 4, 7], [5, 6, 9, 6], [7, 4, 1, 2, 3]])
24
>>> maximum_descent([[13], [1, 8]])
21
>>> maximum_descent([])
0
>>> maximum_descent([[15], [12, 9], [15, 11, 6]])
42
>>> maximum_descent([[4], [9, 4], [3, 8, 4], [9, 3, 2, 10]])
25
>>> maximum_descent([[15], [3, 11], [13, 10, 6], [15, 14, 8, 1], [0, 2, 12, 0, 15]])
62
>>> maximum_descent([[10], [7, 10], [2, 6, 7], [7, 4, 14, 2], [2, 10, 15, 3, 9], [9, 3, 10, 6, 9, 14]])
66