6.1 Dynamisk programmering — mekanikk

Overlappende delproblemer + optimal substruktur, memoisering vs. bottom-up, og rekonstruksjon av selve løsningen (ikke bare verdien) via lagrede beslutninger.

55 min

8 oppgaver

Dynamisk programmeringmekanikk

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk

Brukes videre i

6.2DP-klassikere — stavkapping, LCS og ryggsekk 6.4Grådighet — Huffman og aktivitetsutvelgelse

Dynamisk programmering er en av de to designryggradene i faget, og temaet er registrert i 94 % (16 av de 17 settene i grunnlaget). Grunnlaget er de 17 settene fra august 2015 til august 2023 som er gjennomgått tema for tema — det er nevneren hver gang boka oppgir en prosent.

Tre oppgavesjangre henter fra dette kapitlet, og de skrives ut i klarspråk her fordi de går igjen resten av boka:

- Sjanger F — «stemmer dette?»: du får en påstand og skal svare ja eller nei først, og deretter gi én presis setning. Den klassiske her er: «rekonstruksjon av selve løsningen fra en DP-tabell er gratis — stemmer det?»
- Sjanger G — reduksjon og argument om vanskelighet: du skal si hvilken vei et argument går og hva det faktisk beviser. I dette kapitlet møter du forløperen: hva skillet mellom en avgjørelsesvariant og en optimeringsvariant betyr.
- Sjanger H — åpen algoritmedesign: du får et problem i ny innpakning og skal skissere en algoritme på fem–ti linjer. Mekanikken i dette kapitlet er det du bygger den skissen av.

To innsikter går igjen som faste delspørsmål: når memoisering ikke hjelper (fordi delproblemene ikke gjentar seg), og at rekonstruksjon krever lagrede valg, men uten at kjøretiden vokser.

Prioritet: bør sitte. Regner du med å møte en åpen designoppgave — og det gjør du, de siste oppgavene i hvert ordinære sett er nettopp det — er dette kapitlet i praksis obligatorisk.

Forkunnskaper

Dette kapitlet bygger på rekurrenser og rekursjon:

- kap. 1.1 — de asymptotiske symbolene. Du trenger å kunne lese $\Theta$ , $O$ og $\Omega$ , og vite at $\lg n$ betyr $\log_2 n$ .
- kap. 1.4 og kap. 1.5 — å sette opp og løse en rekurrens. Vi setter opp rekurrenser hele veien her, men vi løser dem sjelden med masterteoremet: DP-rekurrenser deler sjelden problemet i like store biter.
- kap. 2.1 — Merge-Sort. Den brukes som kontrast: et rekursivt problem der delproblemene ikke gjentar seg.

Er rekursjon i seg selv ferskt, er Rekursjon — spore og skrive et mykere første møte. Du trenger ikke mer enn å kunne følge et rekursivt kall med blyant.

Notasjons- og pseudokodeliste

Når det samme regnestykket dukker opp igjen (~15 min)

Du står nederst i en trapp med

n

trinn og kan ta enten ett eller to trinn av gangen. Hvor mange forskjellige måter kan du gå opp på? Spørsmålet er ikke konstruert: det er nøyaktig formen på et ruteproblem, og du løser det uten å tenke etter i det små. Med tre trinn finnes tre måter, med fire finnes fem.

Den naturlige måten å angripe det på er å se på det siste trinnet du tok. Enten kom du fra trinn $n-1$ med ett steg, eller fra trinn $n-2$ med to steg. Ingen andre muligheter finnes, og de to gruppene overlapper ikke. Altså:

$W(n) = W(n-1) + W(n-2), \qquad W(0) = 1,\; W(1) = 1$

Det er fibonaccitallene forskjøvet ett hakk, og rekurrensen kan skrives rett om til et rekursivt program. Problemet er at det programmet er ubrukelig i praksis. For å regne ut $W(n)$ regner det ut $W(n-2)$ to ganger, $W(n-3)$ tre ganger, $W(n-4)$ fem ganger — og arbeidet vokser eksponentielt selv om det bare finnes $n+1$ forskjellige spørsmål å svare på.

Det er kjernen i dynamisk programmering: når de samme delproblemene dukker opp igjen og igjen, lønner det seg å svare på hvert av dem én gang og skrive svaret ned.

Overlappende delproblemer

n

Optimal substruktur

n

Dynamisk programmering

En designteknikk for problemer som har både optimal substruktur og overlappende delproblemer: hvert delproblem løses nøyaktig én gang, og svaret lagres i en tabell som slås opp i senere. Teknikken består alltid av de samme fire delene: definér delproblemet presist, skriv rekurrensen, oppgi grunntilfellene, og velg en rekkefølge å regne dem ut i. Kjøretiden er da antall delproblemer ganget med arbeidet per delproblem. Navnet er historisk og misvisende — «programmering» betyr her planlegging med tabell, ikke koding.

✏️Eksempel 1: Hvor mye arbeid kaster den naive rekursjonen bort?

Naiv-Fib(n) er rekurrensen skrevet rett om til rekursjon, uten noe minne:

Naiv-Fib(n)
  Input:  et heltall n >= 0
  Output: F(n)
  if n <= 1
      return n
  return Naiv-Fib(n-1) + Naiv-Fib(n-2)

Tell antall kall for $n = 0, 1, \dots, 10$ , og tell hvor mange ganger hvert enkelt delproblem løses når du kjører Naiv-Fib(5).

Antall kall totalt:

$n$	0	1	2	3	4	5	6	7	8	9	10
$F(n)$	0	1	1	2	3	5	8	13	21	34	55
Kall	1	1	3	5	9	15	25	41	67	109	177

Hvor mange ganger hvert delproblem løses i Naiv-Fib(5):

Delproblem	$F(5)$	$F(4)$	$F(3)$	$F(2)$	$F(1)$	$F(0)$
Antall ganger løst	1	1	2	3	5	3

Til sammen 15 kall for å svare på seks forskjellige spørsmål.

Legg merke til at kalletallet selv følger fibonaccimønsteret: antall kall for $n$ er antall kall for $n-1$ pluss antall kall for $n-2$ pluss ett. Det vokser derfor like fort som $F(n)$ selv, altså eksponentielt. For $n = 40$ blir det 331 160 281 kall — for å regne ut 41 forskjellige tall.

Svaret oppgaven ber om: 15 kall for $n=5$ , og delproblemene løses 1, 1, 2, 3, 5 og 3 ganger. Det er den observasjonen som gjør dynamisk programmering aktuell — ikke tallene i seg selv.

📝Oppgave 1

Sjanger D

Forklar med egne ord forskjellen på optimal substruktur og overlappende delproblemer, og si hvorfor dynamisk programmering krever begge.

Memoisering og tabellutfylling — to veier, samme kjøretid (~15 min)

Det finnes to måter å realisere en dynamisk programmering på, og eksamensoppgaver ber deg jevnlig sammenligne dem. De gir samme svar og samme asymptotiske kjøretid; forskjellen er hvem som styrer rekkefølgen.

Memoisering

Memoisering er den rekursive varianten av dynamisk programmering, ovenfra og ned: du beholder den naturlige rekursjonen, men legger inn en tabell som husker svar. Første gang et delproblem løses, skrives svaret inn i tabellen; hvert senere kall slår bare opp. Fordelen er at du bare regner ut de delproblemene som faktisk trengs. Ulempen er kall-overheadet og at rekursjonsdybden kan bli stor. Ordet kommer av memo, altså notat — det er ikke en stavefeil for «memorisering».

📜Pseudokode-kontrakt: `Memoized-Fib`

1. Antagelser om representasjon. Tabellen er b[0..n], indeksert fra 0 fordi delproblemene selv er nummerert fra 0. Hver celle er enten NIL (ikke løst ennå) eller det ferdige svaret. Tabellen er felles for alle rekursive kall.

2. Pre-/postbetingelse. Før: n >= 0, og b[i] = NIL for alle i. Etter: returverdien er $F(n)$ , og b[i] inneholder $F(i)$ for hvert delproblem i som faktisk ble berørt.

3. Pseudokoden.

Memoized-Fib(n)
  Input:  et heltall n >= 0
  Output: F(n); tabellen b husker delproblemene som er lost
  la b[0..n] vaere en ny tabell
  for i = 0 to n
      b[i] = NIL
  return Memoized-Fib-Aux(b, n)

Memoized-Fib-Aux(b, i)
  Input:  tabellen b og et delproblem i
  Output: F(i), og b[i] er fylt ut
  if b[i] != NIL
      return b[i]
  if i <= 1
      b[i] = i
  else
      b[i] = Memoized-Fib-Aux(b, i-1) + Memoized-Fib-Aux(b, i-2)
  return b[i]

4. Grunnideen i én setning. Hvert delproblem i får høyst ett kall som faktisk regner noe ut — alle senere kall treffer en utfylt celle og returnerer med det samme.

5. Kjøretid. Det finnes $n+1$ delproblemer, hvert av dem gjør konstant arbeid utover de rekursive kallene, og hvert kall som ikke regner ut noe, koster konstant tid: $\Theta(n)$ .

Bottom-up-utfylling

Bottom-up er den iterative varianten, nedenfra og opp: du dropper rekursjonen og fyller tabellen med løkker, i en rekkefølge der hvert delproblem kommer etter alle delproblemene det avhenger av. Fordelen er at det ikke finnes rekursjonsstabel og ikke noe kall-overhead, og at fylleordenen gjør avhengighetene synlige. Ulempen er at du regner ut alle cellene, også de en memoisert løsning ville ha hoppet over. Kjøretiden er den samme som memoisert, opp til konstanter.

📜Pseudokode-kontrakt: `Bottom-Up-Fib`

1. Antagelser om representasjon. Samme tabell b[0..n], men nå fylles den i stigende rekkefølge. Ingen celle leses før den er skrevet.

2. Pre-/postbetingelse. Før: n >= 0. Etter: b[i] = F(i) for hver i fra 0 til n, og returverdien er b[n].

3. Pseudokoden.

Bottom-Up-Fib(n)
  Input:  et heltall n >= 0
  Output: F(n); tabellen b[0..n] er fylt ut i sin helhet
  la b[0..n] vaere en ny tabell
  b[0] = 0
  if n >= 1
      b[1] = 1
  for i = 2 to n
      b[i] = b[i-1] + b[i-2]
  return b[n]

4. Invarianten i én setning. Før hver runde av for-løkka med telleverdi i gjelder at b[0..i-1] inneholder de riktige verdiene $F(0), \dots, F(i-1)$ — derfor er de to cellene løkka leser, allerede ferdige.

5. Kjøretid. Løkka går $n-1$ runder og gjør konstant arbeid per runde: $\Theta(n)$ , altså nøyaktig det samme som den memoiserte varianten.

Hvorfor gir de to variantene samme asymptotiske kjøretid? Argumentet er kort nok til å skrives på eksamen i to setninger, og det er verdt å kunne:

Intuisjon: i begge tilfellene finnes det nøyaktig ett arbeidsstykke per delproblem. Memoiseringen betaler for det første gangen delproblemet møtes; bottom-up betaler for det når løkka kommer dit. Alt annet arbeid — oppslag i en utfylt celle, en løkkerunde som bare leser — er konstant per gang, og antall slike ganger er begrenset av hvor mange kanter delproblemgrafen har.

Regelen du bruker i praksis, er derfor denne, og den gjelder for hver eneste dynamiske programmering du møter i faget:

$\text{kjøretid} = (\text{antall delproblemer}) \times (\text{arbeid per delproblem})$

For trapperekurrensen: $n+1$ delproblemer, konstant arbeid hver, altså $\Theta(n)$ . Har du en tabell med $n$ rader og $m$ kolonner der hver celle koster konstant tid, får du $\Theta(nm)$ . Må hver celle sammenligne $j$ kandidater, får du en sum i stedet, og den summen kan bli $\Theta(n^2)$ .

Den eneste virkelige forskjellen er hvilke celler som fylles. En memoisert løsning som bare trenger halve tabellen, fyller bare halve tabellen. Bottom-up fyller alt. Asymptotisk er det ofte likegyldig, men det er svaret på delspørsmålet «når vil du foretrekke memoisering?»: når mange delproblemer aldri blir spurt om.

✏️Eksempel 2: Samme tabell, tre helt ulike arbeidsmengder

Kjør de tre variantene på trappe-/fibonaccirekurrensen og sammenlign arbeidet. Oppgi antall kall for Naiv-Fib, antall kall for Memoized-Fib og antall tilordninger i løkka til Bottom-Up-Fib.

$n$	`Naiv-Fib`: kall	`Memoized-Fib`: kall	`Bottom-Up-Fib`: løkkerunder	$F(n)$
5	15	9	4	5
10	177	19	9	55
20	21 891	39	19	6 765
30	2 692 537	59	29	832 040
40	331 160 281	79	39	102 334 155

Begge de to DP-variantene gir samme ferdige tabell. For

n = 10

:
b[0..10]

= [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

— identisk om den fylles ovenfra og ned eller nedenfra og opp.
Lesning av tallene: Naiv-Fib bruker et antall kall som selv følger fibonaccirekurrensen, altså eksponentiell vekst. Memoized-Fib bruker

2n-1

kall for

n \ge 1

: ett kall per delproblem pluss ett oppslagskall per kant i delproblemgrafen. Bottom-Up-Fib bruker

n-1

løkkerunder. De to siste kolonnene skiller seg med en konstant faktor — det er nettopp derfor begge er

\Theta(n)

.
Svaret oppgaven ber om er de tre kolonnene. Sammenligningen av Naiv-Fib med de to andre er poenget; sammenligningen av de to DP-variantene med hverandre er en konstantfaktor, ikke en asymptotisk forskjell.

📝Oppgave 2

Eksamensnivå, sjanger E

En dynamisk programmering har $n \cdot m$ delproblemer, og hvert delproblem sammenligner et konstant antall kandidater. Oppgi kjøretiden på strammest mulig form, og skriv den ene setningen som begrunner den.

📝Oppgave 3

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene. Svar ja eller nei først, deretter én setning.

a) En memoisert løsning har alltid lavere asymptotisk kjøretid enn den tilsvarende bottom-up-løsningen, fordi den hopper over delproblemer.
b) En bottom-up-løsning trenger en fylleorden der hvert delproblem kommer etter alle delproblemene det avhenger av.

Typiske feil

Felle #6 — å påstå at rekonstruksjon fra en DP-tabell er «trivielt gratis». Verditabellen alene gir deg tallet, ikke løsningen. Skal du ut med selve oppdelingen, sekvensen eller utvalget, må valgene lagres underveis — eller leses tilbake ut av verditabellen. Det er billig, men det er ikke ingenting, og en fasit som hopper over leddet er ufullstendig. Vi bygger opp svaret i avsnittet om å hente ut selve løsningen.

Å bruke dynamisk programmering der det ikke er overlapp. Har delproblemene ingen gjentakelse, gir memoisering null gevinst og bare ekstra minnebruk. Da er splitt-og-hersk både raskere og enklere.

Å blande optimal substruktur med grådig valg-egenskap. Optimal substruktur sier at hvis du kjenner de optimale delløsningene, kan du bygge helheten av dem — du må fortsatt prøve alle valgene i steget. Grådig valg-egenskap er den mye sterkere påstanden at ett bestemt valg alltid kan tas uten å se på delløsningene. Nesten alle DP-problemer har det første og ikke det andre.

Å glemme at memoisering og bottom-up har samme kjøretid. Det er et fast delspørsmål, og «memoisering er raskere» er galt som asymptotisk påstand.

Når dynamisk programmering ikke slår splitt-og-hersk (~8 min)

Merge-Sort deler arrayet i to halvdeler, sorterer hver av dem og fletter. Den er rekursiv, den har åpenbart optimal substruktur — en sortert helhet består av to sorterte halvdeler — og likevel er memoisering fullstendig bortkastet der.

Grunnen står i høyre halvdel av figuren over: Merge-Sort på åtte elementer løser delproblemene 1..8, 1..4, 5..8, 1..2, 3..4, 5..6 og 7..8. Hvert intervall opptrer nøyaktig én gang. Det finnes ingen celle å slå opp i, fordi ingen spør om det samme to ganger.

Intuisjon: splitt-og-hersk deler inputen i disjunkte biter, og disjunkte biter kan ikke overlappe. Dynamisk programmering blir aktuelt først når delproblemene deler materiale — som i trapperekurrensen, der $W(n-1)$ og $W(n-2)$ begge trenger $W(n-3)$ .

Testen du bruker på eksamen er derfor kort: tegn to nivåer av rekursjonstreet og se om det samme delproblemet dukker opp to steder. Gjør det ikke det, er svaret at memoisering ikke hjelper, og da skal du si det rett ut — det er et av de faste delspørsmålene.

Splitt-og-hersk

T(n) = 2T(n/2) + \Theta(n) = \Theta(n\lg n)

📝Oppgave 4

Eksamensnivå, sjanger F

En student foreslår å memoisere Merge-Sort for å gjøre den raskere. Svar ja eller nei på om det hjelper, og begrunn i én til to setninger.

Å hente ut selve løsningen, ikke bare verdien (~12 min)

En vaktsentral setter opp turnus for en uke. For hver natt

i

finnes et tillegg

p_i

, men reglene sier at ingen kan ta to netter på rad. Hvilke netter skal du melde deg på for å tjene mest mulig?

Rekurrensen faller ut av det samme grepet som i trappen — se på det siste valget. Enten står du over natt $i$ , og da er det beste du kan få, det beste for de $i-1$ første nettene. Eller så tar du natt $i$ , og da må natt $i-1$ stå over:

$b[i] = \max\big(b[i-1],\; b[i-2] + p_i\big), \qquad b[0] = 0,\; b[1] = p_1$

Her ligger fellen som eksamen faktisk tester. b[n] gir deg beløpet. Det gir deg ikke vaktlisten. Og det er vaktlisten sjefen din vil ha.

Felle #6 — å påstå at rekonstruksjonen er trivielt gratis — er nettopp dette: leddet som mangler i en ellers riktig besvarelse. Retten på det er enkel, men den må skrives: hver gang rekurrensen gjør et valg, lagrer du valget i en egen tabell s. Etterpå leser du s baklengs.

Rekonstruksjon

O(n)

Valgtabell

En tabell s som lagres ved siden av verditabellen b, og som for hvert delproblem husker hvilket valg som ga den beste verdien. I vaktliste-rekurrensen er s[i] enten «ta natt i » eller «hopp over». I en oppdelingsrekurrens er s[j] lengden på det første stykket. I en tabell over to sekvenser er s[i,j] en retning: skrått, opp eller til venstre. Å fylle s koster konstant tid ekstra per celle, altså ingen asymptotisk endring — og det er det som gjør rekonstruksjonen billig.

📜Pseudokode-kontrakt: `Print-Solution`

1. Antagelser om representasjon. Verditabellen b[0..n] og valgtabellen s[1..n] er begge ferdig utfylt av utfyllingsfasen. s[i] er enten TA eller HOPP. Vi bruker vaktliste-rekurrensen som bærer, men mønsteret er det samme for alle DP-er med ett valg per celle.

2. Pre-/postbetingelse. Før: b og s er fylt ut for alle i fra 1 til n. Etter: rutinen har skrevet ut nøyaktig de nettene som inngår i en optimal vaktliste, i stigende rekkefølge, og tabellene er urørt.

3. Pseudokoden.

Extended-Bottom-Up-Shifts(p, n)
  Input:  betalingene p[1..n]
  Output: verditabellen b[0..n] og valgtabellen s[1..n]
  la b[0..n] og s[1..n] vaere nye tabeller
  b[0] = 0
  for i = 1 to n
      if i == 1
          ta = p[1]
      else
          ta = b[i-2] + p[i]
      if ta > b[i-1]
          b[i] = ta
          s[i] = TA
      else
          b[i] = b[i-1]
          s[i] = HOPP
  return b, s

Print-Solution(s, i)
  Input:  valgtabellen s og et delproblem i
  Output: nettene i en optimal vaktliste, i stigende rekkefolge
  if i <= 0
      return
  if s[i] == TA
      Print-Solution(s, i-2)
      skriv ut i
  else
      Print-Solution(s, i-1)

4. Grunnideen i én setning. Hvert kall flytter seg minst ett hakk nedover i tabellen og skriver ut høyst ett tall, så utskriften er nøyaktig valgene langs den optimale kjeden fra n og ned til grunntilfellet.

5. Kjøretid. Print-Solution gjør høyst n kall med konstant arbeid hver, altså $O(n)$ — samme orden som utfyllingen selv, og derfor øker den ikke den asymptotiske kjøretiden. Å fylle s koster konstant tid ekstra per celle og endrer heller ingenting.

✏️Eksempel 3: Vaktlisten — verdien er ikke svaret

En uke har sju netter med tilleggene

$p = [4,\; 11,\; 8,\; 3,\; 9,\; 6,\; 7]$

Ingen kan ta to netter på rad. Fyll tabellene $b$ og $s$ , oppgi det største samlede tillegget, og oppgi hvilke netter som gir det.

Utfyllingen, natt for natt:

Steg $i$	$p_i$	Hopp over: $b[i-1]$	Ta natt $i$ : $b[i-2]+p_i$	$b[i]$	Lagret valg $s[i]$
1	4	0	4	4	ta natt 1
2	11	4	11	11	ta natt 2
3	8	11	12	12	ta natt 3
4	3	12	14	14	ta natt 4
5	9	14	21	21	ta natt 5
6	6	21	20	21	hopp over
7	7	21	28	28	ta natt 7

b[0..7] = [0, 4, 11, 12, 14, 21, 21, 28]

Rekonstruksjonen, lest baklengs fra

s[7]

s[7]

sier ta, så natt 7 er med, og vi hopper til

i=5

s[5]

sier ta, så natt 5 er med, og vi hopper til

i=3

s[3]

sier ta, natt 3 er med, videre til

i=1

s[1]

sier ta, natt 1 er med.
Svaret:
- Største samlede tillegg: 28.
- Vaktlisten: nettene 1, 3, 5 og 7.
Merk hva oppgaven ber om. Den ber om både beløpet og listen. Hadde du bare levert 28, ville halve svaret manglet — og det er nettopp felle #6. Legg også merke til at

s[6]

er det eneste hopp over-valget: der er

b[5] = 21

større enn

b[4] + p_6 = 14 + 6 = 20

. Én eneste celle avgjør formen på hele listen.
Kjøretid:

n

delproblemer med konstant arbeid hver gir

\Theta(n)

for utfyllingen, og rekonstruksjonen legger til

O(n)

. Samlet

\Theta(n)

— rekonstruksjonen er altså gratis i asymptotisk forstand, men den krever at

s

ble fylt ut.

📝Oppgave 5

Eksamensnivå, sjanger C

Bruk vaktliste-rekurrensen på tilleggene

$p = [6,\; 3,\; 9,\; 2,\; 8]$

Oppgi tabellen $b[0..5]$ og hvilke netter som inngår i den optimale listen.

📝Oppgave 6

Eksamensnivå, sjanger F

En besvarelse skriver: «Vi fyller tabellen $b$ og leser av $b[n]$ . Selve løsningen får vi gratis ut av tabellen etterpå, så rekonstruksjonen trenger ingen egen omtale.»

Svar ja eller nei på om påstanden holder, og skriv den presise rettelsen i to til tre setninger.

Avgjørelsesvariant og optimeringsvariant (~5 min)

Det samme problemet finnes nesten alltid i to former, og forskjellen blir viktig i kap. 7.1.

Optimeringsvarianten spør etter det beste: «hva er det største samlede tillegget?» Svaret er et tall — eller, hvis du rekonstruerer, en liste.

Avgjørelsesvarianten spør etter ja eller nei: «finnes det en lovlig vaktliste med samlet tillegg minst 25?» Svaret er ett bit.

De to henger tett sammen. Kan du løse optimeringsvarianten, kan du svare på avgjørelsesvarianten ved å sammenligne optimalverdien med grensen. Motsatt vei kan du ofte finne optimalverdien ved å stille avgjørelsesspørsmålet gjentatte ganger med forskjellige grenser.

Grunnen til at skillet finnes, er teknisk: teorien om vanskelige problemer i Del 7 er bygget på avgjørelsesproblemer, fordi et ja/nei-svar lar seg verifisere presist. Når du senere leser at et problem er NP-komplett, er det alltid avgjørelsesvarianten som omtales.

Avgjørelsesproblem

\Theta(n)

Optimeringsproblem

Et problem der svaret er den beste løsningen — den største verdien, den korteste stien, den billigste oppdelingen — eventuelt sammen med selve løsningen som gir den. Nesten alle problemene i Del 6 er optimeringsproblemer, og alle har en tilhørende avgjørelsesvariant med en grense innbakt. Å konvertere mellom dem er en fast liten øvelse. Merk at «hva er verdien?» og «hvilken løsning gir verdien?» er to forskjellige spørsmål med samme kjøretid — det siste krever rekonstruksjon.

📝Oppgave 7

Eksamensnivå, sjanger D

Formulér avgjørelsesvarianten av vaktlisteproblemet presist, og forklar i én setning hvordan du svarer på den når du allerede har fylt tabellen $b$ .

📝Oppgave 8

Eksamensnivå, sjanger H

En sykkelverksted-kjede skal velge ut hvilke av $n$ verksteder langs en hovedvei som skal holde søndagsåpent. Verksted $i$ gir et anslått overskudd $g_i$ , men konkurransereglene sier at to verksteder som ligger ved siden av hverandre i rekka, ikke begge kan holde åpent.

Beskriv en algoritme som finner det største samlede overskuddet og hvilke verksteder som skal holde åpent. Svar i designformatet: hvilket klassisk problem dette er, hvilket paradigme du bruker, konstruksjonen, rekonstruksjonen og kjøretiden.

Kjøretidene i dette kapitlet samlet

Algoritme	Beste	Verste	Forventet	Krav/egenskap
`Naiv-Fib(n)`	eksponentiell	eksponentiell	eksponentiell	ingen lagring; antall kall følger selv fibonaccirekurrensen
`Memoized-Fib(n)`	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	krever tabell `b[0..n]`; regner bare ut delproblemer som etterspørres
`Bottom-Up-Fib(n)`	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	krever fylleorden der avhengighetene kommer først; fyller hele tabellen
Vaktliste-DP (utfylling)	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	optimal substruktur og overlapp; gir bare optimalverdien
`Print-Solution(s, n)`	$O(n)$	$O(n)$	$O(n)$	krever utfylt valgtabell `s`; øker ikke kjøretiden til utfyllingen
`Merge-Sort(A, 1, n)`	$\Theta(n\lg n)$	$\Theta(n\lg n)$	$\Theta(n\lg n)$	splitt-og-hersk, ingen overlapp — memoisering gir null gevinst

Den generelle regelen står over de enkelte radene: kjøretiden til en dynamisk programmering er antall delproblemer ganger arbeidet per delproblem. Klarer du å oppgi de to faktorene, har du kjøretiden — og du har den på en form du kan begrunne, ikke bare huske.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder kjernestoffet.

Delproblemrom

n+1

Delproblemgraf

n+1

Fylleorden

Rekkefølgen en bottom-up-løsning fyller tabellen i: hvert delproblem må komme etter alle delproblemene det avhenger av. I praksis er det som regel stigende indeks, økende delproblemstørrelse, eller rad for rad i en todimensjonal tabell. Formelt er det en topologisk sortering av delproblemgrafen. Feil fylleorden gir en løsning som leser tomme celler — og det er en av de vanligste feilene når man skriver DP-en ut i detalj i stedet for å skissere den.

Grunntilfelle i en DP-rekurrens

De minste delproblemene, som har svar uten rekursjon: b[0] = 0, c[i,0] = 0, «en tom stav er verdt null». De skal alltid oppgis eksplisitt. En rekurrens uten grunntilfeller er ufullstendig, og en fasit som hopper over dem, mister et delpoeng: rekurrensen alene definerer ikke noen verdi. Det er også her av-én-feilene bor. Sjekk alltid det minste tilfellet for hånd før du oppgir en rekurrens.

Naiv rekursjon uten lagring

Rekurrensen skrevet rett om til rekursive kall, uten noen tabell. Kjøretiden blir antall kall, ikke antall delproblemer — og på et problem med overlapp er det tallet typisk eksponentielt. Naiv-Fib(40) gjør 331 160 281 kall for å regne ut 41 forskjellige tall. Den er likevel nyttig som mellomstasjon: skriv rekurrensen naivt først, se om delproblemene gjentar seg, og legg til tabellen etterpå.

Grådig valg-egenskap

Egenskapen at ett bestemt lokalt valg alltid kan inngå i en optimal løsning, slik at du kan ta valget uten å se på delløsningene. Den er strengt sterkere enn optimal substruktur, og den er sjelden. Har et problem den, trengs ingen tabell — da holder det å ta valgene i riktig rekkefølge, og du får en grådig algoritme. Det er temaet i kap. 6.4 . Å forveksle de to er en fast felle: optimal substruktur lar deg bygge av optimale delløsninger, men du må fortsatt prøve valgene.

Kjøretidsregelen for dynamisk programmering

n

Plassoptimalisering i en DP-tabell

\Theta(n)

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.