Givet en rad med tal, hur ska vi stryka bort tal så att så många som möjligt står kvar och de ändå är i stigande ordning (eller lika).
Ex. Raden är <5 1 4 7 3 3 6>.
Den längsta raden som kan stå kvar är <1 3 3 6>.
Problemet kan ses som att gå igenom serien från vänster till höger och för varje tal göra ett avvägande. Om det går att förlänga en växande serie med det aktuella talet är ju detta visserligen bra, men om talet är högt är det kanske bättre att stryka det för att få med fler tal senare. T.ex. ska algoritmen veta att man inte ska ta med 4:an istället (då blir raden bara <1 4 7>)?
Den dynamiska algoritmen gör just detta, men på ett fegt sätt för att vara säker på att inte välja fel. Antag att man, efter att ha undersökt de k första talen, förutom att ha hittat den längsta stigande sekvensen (längd m) sparat de bästa stigande sekvenserna med längderna 1..m. Den bästa sekvensen av en viss längd är givetvis den som slutar på det lägsta talet eftersom den är lättast att utöka. Notera också att det sista talet i varje serie är lägst i 1-serien och ökar sedan fram till m-serien (kan bevisas).
Om vi nu tittar på det (k+1):te talet, ser vi att några av de sparade serierna går att förlänga med detta tal (om inte annat går alltid 0-serien att förlänga till 1). Om vi kan förlänga m-serien är det givetvis det bästa, då är vi färdiga. Men antag istället att den längsta serien som går att förlänga med talet, har längden p. Då kan vi ju förlänga denna till längden p+1. Eftersom det inte gick att förlänga den förra (p+1)-serien måste denna nya (p+1)-serie vara "bättre". Så då kan vi ersätta den förra med den nya och om p=m öka m med 1. Observera att det inte är någon idé att förlänga de kortare serierna. Om t.ex. (p-1)-serien skulle förlängas med det aktuella talet skulle den nya p-serien inte vara bättre än den gamla eftersom den också gick att förlänga.
Algoritmen blir alltså något sånt här:
A[1..n] är den ursprungliga listan
Vi sparar serierna i S[1..n]. Varje serie S[i] bör
helst sparas som en länkad lista för effektivitet. Jag utelämnar
detaljerna för detta, och tar fram det sista elementet i S[i]
med S[i].last .
LIS(A, n)
m := 0
S[0] := NIL
for k := 1 to n do
p := m
while (p > 0) and (S[p].last
> A[k]) do
p := p - 1 ***
S[p+1] := (S[p] med A[k] tillagt på slutet av listan)
if p = m then m := m + 1
return S[m]
Om man har väldigt ont om exekveringstid kan man notera att sökningen efter det största sistatalet som är <= A[k] (raden märkt med ***) sker i en sorterad miljö, varför binär sökning kan användas, dvs man går inte konstant neråt med 1 utan hoppar först till mitten och jämför, sedan till mitten av den hälft som befanns rätt vid första jämförelsen osv. Blir krångligare att skriva.
Detta var återigen ett ganska enkelt exempel men ändå ett typiskt dynamiskt exempel. Istället för att bara spara en sak, sparar vi en massa information hela tiden, eftersom den säkert kan vara bra att ha.
Övningsuppgift
Använd dynamisk programmering för att hitta den längsta gemensamma sekvensen i två talföljder A och B (här ska man alltså inte stryka tal). Ex. om A = <4 7 3 5 4> och B = <5 3 5 7 4> är längsta gemensamma sekvensen <3 5>