CMD + K
Algoritmer og datastrukturer
CMD + K
Tilbake til Algoritmer og datastrukturer
TDT4120 · Dynamisk programmering
Fyll DP-tabellen
Hver celle er ett delproblem, løst én gang. Følg avhengighetene som hvert svar bygges fra — og spor så den optimale løsningen tilbake ut.
Rader = streng Y · kolonner = streng X.
NåAvhenger avLøsning
∅
A
G
C
A
T
∅
0
0
0
0
0
0
G
0
A
0
C
0
1 / 23Grunntilfelle: et tomt prefiks har LCS-lengde 0 — fyll rad 0 og kolonne 0.
RekurrensX = AGCAT · Y = GAC
c[i][j] = 0 if i=0 or j=0
= c[i−1][j−1] + 1 if X[j] = Y[i]
= max(c[i−1][j], c[i][j−1]) otherwise
—
Relaterte kapitler