I denna handledning lär du dig vad dynamisk programmering är. Du hittar också jämförelsen mellan dynamisk programmering och giriga algoritmer för att lösa problem.
Dynamisk programmering är en teknik i datorprogrammering som hjälper till att effektivt lösa en klass av problem som har överlappande delproblem och optimal underkonstruktionsegenskap.
Sådana problem innebär att man upprepade gånger beräknar värdet på samma delproblem för att hitta den bästa lösningen.
Exempel på dynamisk programmering
Ta fallet med att generera Fibonacci-sekvensen.
Om sekvensen är F (1) F (2) F (3) … F (50) följer den regeln F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46) …
Lägg märke till hur det finns överlappande delproblem, vi måste beräkna F (48) för att beräkna både F (50) och F (49). Detta är exakt den typ av algoritm där dynamisk programmering lyser.
Hur dynamisk programmering fungerar
Dynamisk programmering fungerar genom att lagra resultatet av delproblem så att när deras lösningar krävs är de till hands och vi behöver inte omberäkna dem.
Denna teknik för att lagra värdet på delproblem kallas memoization. Genom att spara värdena i matrisen sparar vi tid för beräkningar av underproblem som vi redan har stött på.
var m = karta (0 → 0, 1 → 1) funktion fib (n) om tangenten n inte finns i kartan mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Dynamisk programmering genom memoization är en top-down-metod för dynamisk programmering. Genom att vända den riktning algoritmen fungerar, dvs. genom att starta från basfallet och arbeta mot lösningen, kan vi också implementera dynamisk programmering på ett nedifrån och upp-sätt.
funktion fib (n) om n = 0 returnerar 0 annat var prevFib = 0, currFib = 1 upprepning n - 1 gånger var newFib = prevFib + currFib prevFib = currFib currFib = newFib returströmFib
Rekursion mot dynamisk programmering
Dynamisk programmering tillämpas mestadels på rekursiva algoritmer. Detta är inte en slump, de flesta optimeringsproblemen kräver rekursion och dynamisk programmering används för optimering.
Men inte alla problem som använder rekursion kan använda dynamisk programmering. Såvida det inte finns överlappande delproblem som i Fibonacci-sekvensproblemet, kan en rekursion bara nå lösningen med en delnings- och erövringsstrategi.
Det är anledningen till att en rekursiv algoritm som Merge Sort inte kan använda dynamisk programmering, eftersom delproblemen inte överlappar varandra på något sätt.
Giriga algoritmer vs dynamisk programmering
Giriga algoritmer liknar dynamisk programmering i den meningen att de båda är verktyg för optimering.
Giriga algoritmer letar dock efter lokala optimala lösningar eller med andra ord ett girigt val i hopp om att hitta ett globalt optimalt. Därför kan giriga algoritmer göra en gissning som ser optimal ut vid den tiden men blir kostsam längs linjen och inte garanterar ett globalt optimalt.
Dynamisk programmering, å andra sidan, hittar den optimala lösningen på delproblem och gör sedan ett välgrundat val för att kombinera resultaten av dessa delproblem för att hitta den mest optimala lösningen.
