Dynamisk programmering: fyll tabellen

Hvorfor er rekursiv Fibonacci så treg, og hva fikser dynamisk programmering? Det rekursive treet for fib av fem eksploderer til femten kall — samme delproblem regnes igjen og igjen. Dynamisk programmering snur problemet på hodet: en tabell fylles nedenfra, hver celle pluss-er sammen de to forrige, hver delsvar lagres én gang. Femten kall mot seks celler — eksponentiell mot lineær. Vist med en levende rekursjonstre der duplikate fib-noder lyser rose, og en DP-tabell der pilene fra forrige to celler tegnes inn før hvert nytt svar dukker opp.