Dinamično programiranje: primeri, pogosti problemi in rešitve

Nobenega dvoma ni, da lahko težave z dinamičnim programiranjem zelo zastrašujejo v kodiranju. Tudi če morda veste, da je treba težavo rešiti z metodo dinamičnega programiranja, je izziv, če lahko v omejenem časovnem okviru najdete delujočo rešitev.

Najboljši način, kako biti dober v težavah z dinamičnim programiranjem, je, da jih prebrodite čim več. Čeprav vam ni treba zapomniti rešitve za vsak problem, je dobro, če imate idejo, kako se lotiti njegovega izvajanja.

Kaj je dinamično programiranje?

Preprosto povedano, dinamično programiranje je metoda optimizacije rekurzivnih algoritmov, ki se večinoma uporabljajo za reševanje računalniških ali matematičnih problemov.

Lahko ga pokličete tudi algoritemska tehnika za reševanje optimizacijskega problema, tako da ga razbijete na enostavnejše pod-probleme. Ključno načelo, na katerem temelji dinamično programiranje, je, da je optimalna rešitev problema odvisna od rešitev njenih podproblemov.

Kjer koli vidimo rekurzivno rešitev, ki ponavlja ponavljajoče se klice za iste vhode, jo lahko optimiziramo z dinamičnim programiranjem. Ideja je preprosto shraniti rezultate podproblemov, tako da jih kasneje ni treba ponovno izračunati.

Dinamično programirane rešitve imajo polinomsko kompleksnost, ki zagotavlja veliko hitrejši čas delovanja kot druge tehnike, kot sta rekurzija ali povratno sledenje. V večini primerov dinamično programiranje zmanjšuje časovno zapletenost, znano tudi kot velik-O, od eksponentnega do polinoma.

Kaj je zapis Big-O?

Vaša koda mora biti učinkovita, kako pa lahko pokažete, kako učinkovita je nekaj? Z Big-O!

Zdaj, ko dobro veste, kaj je dinamično programiranje, je čas, da preverite nekaj pogostih težav in njihove rešitve.

Težave z dinamičnim programiranjem

1. Nahrbtnik problem

Izjava o težavi

Glede na nabor predmetov, vsak s težo in vrednostjo, določite število posameznih predmetov, ki jih želite vključiti v zbiranje, tako da skupna teža ne preseže določene meje in je skupna vrednost tako velika kot mogoče.

Dobili ste dve celoštevilski matriki vrednosti [0..n-1] in uteži [0..n-1] ki predstavljajo vrednosti in uteži, povezane z n postavkami. Podano je tudi celo število W kar predstavlja zmogljivost nahrbtnika.

Tu rešujemo težavo z nahrbtnikom 0/1, kar pomeni, da se lahko odločimo, ali bomo dodali element ali ga izključili.

Algoritem

• Ustvari dvodimenzionalno polje z n + 1 vrstice in w + 1 stolpci. Številka vrstice n označuje nabor elementov od 1 do jazin številko stolpca w označuje največjo nosilnost vrečke.
• Številska vrednost pri [i] [j] označuje skupno vrednost predmetov do jaz v vrečki, ki lahko nosi največ j.
• Na vsaki koordinati [i] [j] v polju izberite največjo vrednost, brez katere lahko dobimo postavka i, ali največjo vrednost, s katero lahko dobimo postavka ikar je večje.
• Največja možna vrednost, vključena v postavko i, je vsota postavke jaz in največjo vrednost, ki jo je mogoče dobiti s preostalo zmogljivostjo nahrbtnika.
• Izvajajte ta korak, dokler ne najdete največje vrednosti za W^th vrstici.

Koda

def FindMax (W, n, vrednosti, uteži):
MaxVals = [[0 za x v območju (W + 1)] za x v območju (n + 1)]
za i v območju (n + 1):
za w v območju (W + 1):
če je i == 0 ali w == 0:
MaxVals [i] [w] = 0
uteži elif [i-1] <= w:
MaxVals [i] [w] = max (vrednosti [i-1]
+ MaxVals [i-1] [w-uteži [i-1]], 
MaxVals [i-1] [w])
sicer:
MaxVals [i] [w] = MaxVals [i-1] [w]
vrnitev MaxVals [n] [W]

2. Problem zamenjave kovancev

Izjava o težavi

Recimo, da ste dobili niz številk, ki predstavljajo vrednosti vsakega kovanca. Glede na določen znesek poiščite najmanjše število kovancev, ki so potrebni za to količino.

Algoritem

• Inicializirajte polje velikosti n + 1, kjer je n znesek. Inicializirajte vrednost vsakega indeksa jaz v polju, da je enak znesku. To označuje največje število kovancev (z uporabo kovancev apoena 1), ki so potrebni za sestavljanje tega zneska.
• Ker ni vrednosti za 0, inicializiramo osnovni primer, kjer matrika [0] = 0.
• Za vsak drugi indeks jaz, primerjamo vrednost v njem (ki je prvotno nastavljena na n + 1) z vrednostjo matrika [i-k] +1, kje k je manj kot jaz. Ta v bistvu preveri celotno matriko do i-1 in poišče najmanjše možno število kovancev, ki jih lahko uporabimo.
• Če je vrednost pri kateri koli matrika [i-k] + 1 je manjša od obstoječe vrednosti pri matrika [i], vrednost nadomestite z matrika [i] s tisto pri matrika [i-k] +1.

Koda

def coin_change (d, znesek, k):
številke = [0] * (znesek + 1)
za j v območju (1, znesek + 1):
najmanj = znesek
za i v območju (1, k + 1):
če (j> = d [i]):
najmanj = min (najmanj, 1 + številke [j-d [i]])
števila [j] = najmanj
povratne številke [znesek]

3. Fibonacci

Izjava o težavi

Fibonaccijeva serija je zaporedje celih števil, kjer je naslednje celo število v seriji vsota prejšnjih dveh.

Opredeljen je z naslednjim rekurzivnim razmerjem: F (0) = 0, F (n) = F (n-1) + F (n-2), kje F (n) je n^th izraz. V tej težavi moramo generirati vsa števila v Fibonaccijevem zaporedju do danega n^th izraz.

Algoritem

• Najprej uporabite rekurzivni pristop za izvedbo danega relativnega odnosa.
• Rekurzivno reševanje tega problema pomeni razčlenitev F (n) v F (n-1) + F (n-2)in nato s funkcijo pokličete funkcijo F (n-1) in F (n + 2) kot parametri. To počnemo do osnovnih primerov, kjer n = 0, ali n = 1 so doseženi.
• Zdaj uporabljamo tehniko, imenovano spominjanje. Rezultate vseh klicev funkcij shranite v matriko. To bo zagotovilo, da bo za vsakih n F (n) je treba izračunati samo enkrat.
• Za vse nadaljnje izračune lahko njegovo vrednost preprosto dobimo iz polja v konstantnem času.

Koda

def fibonacci (n): 
fibNums = [0, 1] 
za i v območju (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
vrni fibNum [n] 

4. Najdaljše naraščajoče zaporedje

Izjava o težavi

Poiščite dolžino najdaljše naraščajoče podsekvence znotraj dane matrike. Najdaljše naraščajoče podsledje je podpolje znotraj niza števil z naraščajočim vrstnim redom. Številke znotraj zaporedja morajo biti unikatne in naraščajoče.

Tudi elementov zaporedja ni treba zaporedoma.

Algoritem

• Začnite z rekurzivnim pristopom, kjer izračunate vrednost najdaljše naraščajoče zaporedje vsaka možna podniz iz indeksa nič v indeks i, kjer je i manjši ali enak velikosti matriko.
• Če želite to metodo spremeniti v dinamično, ustvarite matriko za shranjevanje vrednosti za vsako zaporedje. Inicializirajte vse vrednosti te matrike na 0.
• Vsak indeks jaz te matrike ustreza dolžini najdaljše naraščajoče podsekvence za podniz velikosti jaz.
• Zdaj pa za vsak rekurzivni klic findLIS (arr, n), preverite n^th indeks polja. Če je ta vrednost 0, izračunajte vrednost z uporabo metode v prvem koraku in jo shranite na n^th indeks.
• Končno vrnite največjo vrednost iz polja. To je dolžina najdaljše naraščajoče podsekvence dane velikosti n.

Koda

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
za i v območju (1, n):
za j v območju (0, i):
če myArray [i]> myArray [j] in lis [i] lis [i] = lis [j] +1
maxVal = 0
za i v območju (n):
maxVal = max (maxVal, lis [i])
vrnitev maxVal

Rešitve težav z dinamičnim programiranjem

Zdaj, ko ste šli skozi nekatere najbolj priljubljene težave z dinamičnim programiranjem, je čas, da poskusite rešitve implementirati sami. Če ste zataknjeni, se lahko vedno vrnete in se za vsako zgornjo težavo obrnete na razdelek o algoritmu.

Glede na to, kako priljubljene so tehnike, kot sta rekurzija in dinamično programiranje danes, ne bo škodovalo, če si ogledate nekatere priljubljene platforme, kjer se lahko naučite takšnih konceptov in izpopolnite svoje kodiranje. Čeprav se s temi težavami morda ne boste srečevali vsak dan, jih boste zagotovo srečali na tehničnem razgovoru.

Seveda bo znanje o pogostih težavah zagotovo prineslo dividende, ko se boste odpravili na naslednji razgovor. Torej odprite svoj najljubši IDEin začnite!

9 najboljših kanalov YouTube, ki se učijo programiranja

Ste pripravljeni na kodiranje? Ti kanali v YouTubu so odličen način za začetek razvoja iger, aplikacij, spleta in drugega.

O avtorju