Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Dynamisk programmering, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En metode for problemer med overlappende delinstanser: regn ut hvert deltilfelle én gang og gjenbruk svaret.
Når en rekursiv løsning løser de samme deltilfellene mange ganger. Da lønner det seg å lagre svarene.
Egenskapen at en optimal løsning er bygd av optimale løsninger på delinstansene.
Top-down DP: en rekursiv funksjon som lagrer (huskelagrer) svar den allerede har regnet ut.
Å fylle en tabell over delinstanser i en rekkefølge der hvert behov allerede er regnet ut.
Den lengste sekvensen som forekommer (ikke nødvendigvis sammenhengende) i to strenger. Klassisk DP-tabell.
Å kappe en stav i biter for å maksimere salgsverdi gitt en prisliste. Eksemplet som introduserer DP.
Å velge gjenstander med verdi og vekt slik at total verdi maksimeres innenfor en vektgrense, der hver gjenstand tas helt eller ikke.
Å spore tilbake gjennom DP-tabellen for å finne ikke bare den optimale verdien, men selve den optimale løsningen.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Stavkapping
Den beste inntekten for en stav av lengde er det beste over alle førstekutt , pluss den optimale løsningen for resten. Overlappende delinstanser gjør DP naturlig.
Lengste felles delsekvens
LCS-tabellen bygges opp fra mindre prefikser: matcher tegnene, øk diagonalen med 1; ellers ta det beste av å droppe ett tegn fra hver streng.
0/1-ryggsekkproblemet
For hver gjenstand velger vi det beste av å droppe den eller å ta den (hvis den får plass). Gir en pseudopolynomiell -løsning.
Antall delinstanser
DP er effektivt nettopp fordi tabellen har polynomielt mange celler, og hver fylles i konstant eller polynomiell tid — ulikt det eksponentielle rekursjonstreet.
Optimal delstruktur
En optimal løsning bygger på optimale løsninger av delinstansene. Uten denne egenskapen virker verken DP eller grådighet.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare hva overlappende delinstanser og optimal delstruktur er, og hvorfor begge må gjelde for at DP skal virke
- 02Skille memoisering (top-down) fra iterativ tabellfylling (bottom-up) og begrunne at de gir samme svar og kjøretid
- 03Fylle ut og tolke en LCS-tabell, og rekonstruere selve delsekvensen ved tilbakesporing
- 04Sette opp rekurrensen for 0/1-ryggsekk og forklare hvorfor Θ(nW) er pseudopolynomiell