Redigerer Dynamisk programmering (avsnitt)

== Eksempler ==
Nedenfor er et eksempel.
=== Fibonacci-tallene ===
Fibonacci-tallene er <math>0,1,1,2,3,5,8, \ldots</math>, der hvert tall er lik summen av de 2 forrige tallene. Dynamisk programmering kan brukes til å regne ut <math>F_n</math> raskere enn en naiv implementasjon. Første skritt er å finne den rekursive sammenhengen mellom Fibonacci-tallene. Den er gitt ved:
:<math>F_n = F_{n-1} + F_{n-2}</math>
Å implementere dette direkte vil føre til eksponentiell kjøretid <math>\mathcal{O}(\alpha^n)</math>, der <math>\alpha</math> er en konstant. En direkte, naiv implementasjon er ikke ideell fordi delproblemer blir løst flere ganger. Etter å ha funnet den rekursive sammenhengen er neste skritt å løse initial-problemene:
:<math>F_0 = 0</math>
:<math>F_1 = 1</math>
Dersom vi løser <math>F_{n-1}</math> før <math>F_{n}</math> for alle <math>n</math>, vil kjøretiden være <math>\mathcal{O}(n)</math>. Man starter med å løse <math>F_2</math>, deretter <math>F_3</math>, og så videre. Dette krever lineær tid i <math>n</math>, og man trenger heller ikke mye plass i minnet.

=== Binominalkoeffisientene ===
Binominalkoeffisientene er koeffisientene man får dersom man utvider uttrykket <math>\left ( a+b \right )^n</math>, og skrives som <math>\tbinom{n}{r}</math>. Eksempelvis er <math>\tbinom{3}{2} = 3</math>, fordi det andre leddet i <math>\left ( a+b \right )^3 = a^3 + 3a^2b + 3ab^2 + b^3</math> har koeffisienten <math>3</math>. Sagt på en annen måte teller <math>\tbinom{n}{r}</math> antall måter vi kan velge <math>r</math> elementer fra en samling med <math>n</math> elementer. En naiv implementasjon ville vært å bruke formelen:
:<math>\binom{n}{r} = \frac{n!}{(n-r)! r!}</math>
Problemet er at man potensielt gjør store utregninger av <math>n!</math> som er tidkrevende for en datamaskin. <math>\tbinom{n}{n} = 1</math>,
men en datamaskin må utføre <math>n</math> multiplikasjoner for å regne dette ut. Et bedre utgangspunkt er den rekursive formelen:
:<math>  \binom nk = \binom{n-1}{k-1} + \binom{n-1}k </math>
med startverdier
:<math>\binom n0 = \binom nn = 1</math>
Dette gir utgangspunktet for en implementasjon ved hjelp av dynamisk programmering. Delproblemene overlapper, med dersom vi løser de i riktige rekkefølge
vil kjøretiden være <math>\mathcal{O}(nr)</math> addisjoner.