Referanseside · Kapittel 15

Begreper & formler

Alle nøkkelbegrepene og formlene fra Dynamisk programmering, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Optimal delstruktur

Et problem der optimale løsninger kan bygges opp fra optimale løsninger av delproblemer.

Logg inn for forklaring

02Overlappende delproblemer

Samme delproblem dukker opp flere ganger — lagring sparer tid.

Logg inn for forklaring

03Memoisering

Lagring av resultater for tidligere beregnede delproblemer.

Logg inn for forklaring

04Tabellbasert DP

Iterativ løsning der man fyller ut en tabell fremfor rekursjon.

Logg inn for forklaring

05Eksempel: Fibonacci

$F (n) = F (n - 1) + F (n - 2)$ kan løses på $O (n)$ med DP i stedet for eksponentielt.

Logg inn for forklaring

Formler

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

F (n) = F (n - 1) + F (n - 2)

Fibonacci med DP

Logg inn for forklaring

r_{n} = 1 \leq i \leq n max (p_{i} + r_{n - i})

Kutting av stenger

Logg inn for forklaring

m [i, j] = i \leq k < j min (m [i, k] + m [k + 1, j] + p_{i - 1} p_{k} p_{j})

Matrisekjedemultiplikasjon

Logg inn for forklaring

Tilbake til kapittelet

CMD + K

CMD + K

Begreper & formler

Begreper

Formler

Fibonacci med DP

Kutting av stenger

Matrisekjedemultiplikasjon

Begreper

Formler

Fibonacci med DP

Kutting av stenger

Matrise­kjede­multiplikasjon

Matrisekjedemultiplikasjon