Dynamisk programmering: Eksempler, vanlige problemer og løsninger

Det er ingen tvil om at dynamiske programmeringsproblemer kan være veldig skremmende i et kodingsintervju. Selv når du kanskje vet at et problem må løses ved hjelp av en dynamisk programmeringsmetode, er det en utfordring å kunne komme opp med en fungerende løsning i en begrenset tidsramme.

Den beste måten å bli god på dynamiske programmeringsproblemer er å gå gjennom så mange av dem du kan. Selv om du ikke nødvendigvis trenger å huske løsningen på alle problemer, er det godt å ha en ide om hvordan du skal implementere en.

Hva er dynamisk programmering?

Enkelt sagt, dynamisk programmering er en optimaliseringsmetode for rekursive algoritmer, hvorav de fleste brukes til å løse databehandling eller matematiske problemer.

Du kan også kalle det en algoritmisk teknikk for å løse et optimaliseringsproblem ved å dele det opp i enklere delproblemer. Et sentralt prinsipp som dynamisk programmering er basert på, er at den optimale løsningen på et problem avhenger av løsningene på delproblemene.

Uansett hvor vi ser en rekursiv løsning som har gjentatte anrop for de samme inngangene, kan vi optimalisere den ved hjelp av dynamisk programmering. Tanken er å bare lagre resultatene av underproblemer slik at vi ikke trenger å beregne dem på nytt når det er nødvendig senere.

Dynamisk programmerte løsninger har en polynomskompleksitet som sikrer en mye raskere kjøretid enn andre teknikker som rekursjon eller backtracking. I de fleste tilfeller reduserer dynamisk programmering tidskompleksitet, også kjent som stor-O, fra eksponentiell til polynom.

Hva er Big-O Notation?

Koden din må være effektiv, men hvordan viser du hvor effektiv noe er? Med Big-O!

Nå som du har en god ide om hva dynamisk programmering er, er det på tide å sjekke ut noen vanlige problemer og løsningene deres.

Dynamiske programmeringsproblemer

1. Ryggsekkproblem

Problemstilling

Gitt et sett med elementer, hver med vekt og verdi, bestemme antallet for hver vare som skal inkluderes i en samling slik at totalvekten ikke overstiger en gitt grense og totalverdien er like stor som mulig.

Du får to heltalsmatriser verdier [0..n-1] og vekter [0..n-1] som representerer verdier og vekter assosiert med henholdsvis n gjenstander. Det er også gitt et heltall W som representerer ryggsekkkapasiteten.

Her løser vi 0/1 ryggsekkproblemet, noe som betyr at vi kan velge å enten legge til en vare eller ekskludere den.

Algoritme

• Lag et todimensjonalt array med n + 1 rader og w + 1 kolonner. Et radnummer n betegner settet fra 1 til Jeg, og et kolonnenummer w angir den maksimale bæreevnen til vesken.
• Den numeriske verdien på [i] [j] angir den totale verdien av varene frem til Jeg i en pose som kan bære en maksimal vekt på j.
• Ved hver koordinat [i] [j] i matrisen, velg den maksimale verdien vi kan oppnå uten vare i, eller den maksimale verdien vi kan oppnå med vare idet som er størst.
• Maksimal oppnåelig verdi ved å inkludere artikkel i er summen av varen Jeg seg selv og den maksimale verdien som kan oppnås med gjenværende kapasitet på ryggsekken.
• Utfør dette trinnet til du finner den maksimale verdien for W^th rad.

Kode

def FindMax (W, n, verdier, vekter):
MaxVals = [[0 for x i området (W + 1)] for x i området (n + 1)]
for jeg innen rekkevidde (n + 1):
for w i rekkevidde (W + 1):
hvis jeg == 0 eller w == 0:
MaxVals [i] [w] = 0
Elif-vekter [i-1] <= w:
MaxVals [i] [w] = max (verdier [i-1]
+ MaxVals [i-1] [w-vekter [i-1]], 
MaxVals [i-1] [w])
ellers:
MaxVals [i] [w] = MaxVals [i-1] [w]
returnere MaxVals [n] [W]

2. Myntendringsproblem

Problemstilling

Anta at du får en rekke tall som representerer verdiene til hver mynt. Gitt et spesifikt beløp, finn minimum antall mynter som trengs for å tjene det beløpet.

Algoritme

• Initialiser en rekke størrelser n + 1, hvor n er beløpet. Initialiser verdien av hver indeks Jeg i matrisen for å være lik beløpet. Dette betegner det maksimale antallet mynter (ved bruk av mynter i benevnelse 1) som kreves for å gjøre opp beløpet.
• Siden det ikke er noen pålydende verdi for 0, initialiser du basissaken der matrise [0] = 0.
• For hver annen indeks Jeg, sammenligner vi verdien i den (som i utgangspunktet er satt til n + 1) med verdien matrise [i-k] +1, hvor k er mindre enn Jeg. Dette sjekker i hovedsak hele matrisen frem til i-1 for å finne et minimum antall mynter vi kan bruke.
• Hvis verdien i det hele tatt matrise [i-k] + 1 er mindre enn den eksisterende verdien på matrise [i], erstatt verdien på matrise [i] med den på matrise [i-k] +1.

Kode

def coin_change (d, beløp, k):
tall = [0] * (beløp + 1)
for j innen rekkevidde (1, mengde + 1):
minimum = beløp
for i innen rekkevidde (1, k + 1):
hvis (j> = d [i]):
minimum = min (minimum, 1 + tall [j-d [i]])
tall [j] = minimum
returnummer [beløp]

3. Fibonacci

Problemstilling

Fibonacci-serien er en sekvens av heltall der neste heltall i serien er summen av de to foregående.

Det er definert av følgende rekursive forhold: F (0) = 0, F (n) = F (n-1) + F (n-2), hvor F (n) er da^th begrep. I dette problemet må vi generere alle tallene i en Fibonacci-sekvens opp til en gitt n^th begrep.

Algoritme

• Bruk først en rekursiv tilnærming til å implementere den gitte gjentakelsesforholdet.
• Rekursiv løsning av dette problemet innebærer å bryte sammen F (n) inn i F (n-1) + F (n-2), og deretter ringe funksjonen med F (n-1) og F (n + 2) som parametere. Vi gjør dette til basissakene hvor n = 0, eller n = 1 nås.
• Nå bruker vi en teknikk som heter memoization. Lagre resultatene av alle funksjonsanrop i en matrise. Dette vil sikre at for hver n F (n) trenger bare å beregnes en gang.
• For eventuelle påfølgende beregninger kan verdien enkelt hentes fra matrisen i konstant tid.

Kode

def retracement (n): 
fibNums = [0, 1] 
for i innen rekkevidde (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
returner fibNums [n] 

4. Lengste økende påfølgende

Problemstilling

Finn lengden på den lengste økende sekvensen i en gitt matrise. Den lengste økende sekvensen er en sekvens i en rekke tall med økende orden. Tallene i sekvensen må være unike og i stigende rekkefølge.

Elementene i sekvensen trenger heller ikke være sammenhengende.

Algoritme

• Start med en rekursiv tilnærming der du beregner verdien av den lengste økende følgen av alle mulige underordninger fra indeks null til indeks i, der i er mindre enn eller lik størrelsen på array.
• For å gjøre denne metoden til en dynamisk, lager du en matrise for å lagre verdien for hver påfølgende. Initialiser alle verdiene til denne matrisen til 0.
• Hver indeks Jeg av denne matrisen tilsvarer lengden på den lengste økende undersekvensen for en undergruppe av størrelse Jeg.
• Nå, for hver rekursive samtale av findLIS (arr, n), Undersøk n^th indeks av matrisen. Hvis denne verdien er 0, beregner du verdien ved hjelp av metoden i første trinn og lagrer den på n^th indeks.
• Til slutt, returner maksimumsverdien fra matrisen. Dette er lengden på den lengste økende undersekvensen av en gitt størrelse n.

Kode

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
for jeg innen rekkevidde (1, n):
for j innen rekkevidde (0, i):
hvis myArray [i]> myArray [j] og lis [i] lis [i] = lis [j] +1
maxVal = 0
for jeg innen rekkevidde (n):
maxVal = max (maxVal, lis [i])
return maxVal

Løsninger på dynamiske programmeringsproblemer

Nå som du har gått gjennom noen av de mest populære dynamiske programmeringsproblemene, er det på tide å prøve å implementere løsningene selv. Hvis du sitter fast, kan du alltid komme tilbake og se algoritmeseksjonen for hvert problem ovenfor.

Gitt hvor populære teknikker som rekursjon og dynamisk programmering er i dag, vil det ikke skade å sjekke ut noen populære plattformer der du kan lære slike konsepter og finpusse kodingsferdighetene dine. Selv om du kanskje ikke støter på disse problemene på daglig basis, vil du sikkert møte dem i et teknisk intervju.

Naturligvis vil kunnskapen om vanlige problemer gi utbytte når du går til ditt neste intervju. Så åpne opp din favoritt IDE, og kom i gang!

De 9 beste koden langs YouTube-kanaler for å lære programmering

Klar til å starte kodingen? Disse YouTube-kanalene er en fin måte å komme i gang med spill, app, nett og annen utvikling.

Om forfatteren