Redigerer Dynamisk programmering (avsnitt)

== Overblikk ==

Dynamisk programmering er en generell teknikk, men implementering på hvert enkelt problem kan være svært annerledes. Dynamisk programmering fungerer kun dersom den underliggende kombinatoriske strukturen er sortert på en eller annen måte. Problemet må kunne deles opp i mindre delproblemer, og disse problemene må overlappe. Dersom delproblemene ikke overlapper kalles teknikken for en ''splitt og hersk'' algoritme.

For å implementere dynamisk programmering må man:
# Identifisere en rekursjon som løser problemet
# Starte med å løse de enkleste tilfellene
# Bygge opp løsningen i en rekkefølge slik at ingen delproblemer blir løst mer enn en gang

Ofte blir utregninger lagret i en tabell, slik at de kan hentes senere. En slik tabell kan være en en-dimensjonal liste, to-dimensjonal matrise, og så videre.