Dinamičko programiranje: primjeri, uobičajeni problemi i rješenja

Nema sumnje da problemi s dinamičkim programiranjem mogu biti vrlo zastrašujući u intervjuu za kodiranje. Čak i kad možda znate da problem treba riješiti metodom dinamičkog programiranja, izazov je moći doći do radnog rješenja u ograničenom vremenskom okviru.

Najbolji način da budete dobri u problemima s dinamičkim programiranjem je proći kroz što više njih. Iako ne morate nužno pamtiti rješenje svakog problema, dobro je imati ideju kako krenuti u provedbu.

Što je dinamičko programiranje?

Jednostavno rečeno, dinamičko programiranje metoda je optimizacije za rekurzivne algoritme, od kojih se većina koristi za rješavanje računalnih ili matematičkih problema.

Također ga možete nazvati algoritamskom tehnikom za rješavanje problema optimizacije rastavljajući ga na jednostavnije pod-probleme. Ključno načelo na kojem se temelji dinamičko programiranje jest da optimalno rješenje problema ovisi o rješenjima njegovih potproblema.

Gdje god vidimo rekurzivno rješenje koje ima ponovljene pozive za iste ulaze, možemo ga optimizirati pomoću dinamičkog programiranja. Ideja je jednostavno pohraniti rezultate potproblema kako ih kasnije ne bismo morali ponovno izračunavati kad je to potrebno.

Dinamički programirana rješenja imaju polinomsku složenost koja osigurava puno brže vrijeme izvođenja od ostalih tehnika poput rekurzije ili povratnog praćenja. U većini slučajeva dinamičko programiranje smanjuje vremenske složenosti, također poznate kao velika-O, od eksponencijalnog do polinoma.

Što je Big-O notacija?

Vaš kôd mora biti učinkovit, ali kako pokazati koliko je nešto učinkovito? Uz Big-O!

Sad kad dobro znate što je dinamičko programiranje, vrijeme je da provjerite nekoliko uobičajenih problema i njihova rješenja.

Problemi s dinamičkim programiranjem

1. Ruksak problem

Izjava o problemu

S obzirom na skup predmeta, svaki s težinom i vrijednošću, odredite broj svake stavke koju ćete uključiti u prikupljanje tako da ukupna težina ne prelazi zadanu granicu, a ukupna vrijednost je velika kao moguće.

Dobili ste dva čitava niza vrijednosti [0..n-1] i težine [0..n-1] koji predstavljaju vrijednosti i težine povezane s n stavki. Također je dan cijeli broj W što predstavlja kapacitet naprtnjače.

Ovdje rješavamo problem 0/1 naprtnjače, što znači da možemo odabrati dodati stavku ili je isključiti.

Algoritam

• Stvorite dvodimenzionalni niz pomoću n + 1 redovi i w + 1 stupaca. Broj reda n označava skup predmeta od 1 do jai broj stupca w označava maksimalnu nosivost vreće.
• Brojčana vrijednost na [i J] označava ukupnu vrijednost predmeta do ja u vrećici koja može nositi maksimalnu težinu j.
• Na svakoj koordinati [i J] u nizu odaberite maksimalnu vrijednost bez koje možemo dobiti stavka i, ili maksimalnu vrijednost pomoću koje možemo dobiti stavka ikoji god je veći.
• Maksimalna vrijednost koja se može dobiti uključivanjem stavke i zbroj je stavke ja sama i maksimalna vrijednost koja se može dobiti s preostalim kapacitetom naprtnjače.
• Izvršite ovaj korak dok ne pronađete maksimalnu vrijednost za W^th red.

Kodirati

def FindMax (W, n, vrijednosti, težine):
MaxVals = [[0 za x u rasponu (W + 1)] za x u opsegu (n + 1)]
za i u rasponu (n + 1):
za w u rasponu (W + 1):
ako je i == 0 ili w == 0:
MaxVals [i] [w] = 0
elif utezi [i-1] <= w:
MaxVals [i] [w] = max (vrijednosti [i-1]
+ MaxVals [i-1] [težine [i-1]], 
MaxVals [i-1] [w])
drugo:
MaxVals [i] [w] = MaxVals [i-1] [w]
povratak MaxVals [n] [W]

2. Problem promjene novčića

Izjava o problemu

Pretpostavimo da ste dobili niz brojeva koji predstavljaju vrijednosti svakog novčića. S obzirom na određeni iznos, pronađite minimalni broj kovanica potrebnih za izradu tog iznosa.

Algoritam

• Inicijalizirajte niz veličine n + 1, gdje je n iznos. Inicijalizirajte vrijednost svakog indeksa ja u nizu da bude jednak iznosu. Ovo označava maksimalan broj kovanica (koristeći kovanice denominacije 1) potreban da se sačini taj iznos.
• Budući da ne postoji denominacija za 0, inicijaliziramo osnovni slučaj gdje niz [0] = 0.
• Za svaki drugi indeks ja, uspoređujemo vrijednost u njemu (koja je u početku postavljena na n + 1) s vrijednošću niz [i-k] +1, gdje k je manje od ja. Ovo u osnovi provjerava čitav niz do i-1 kako bi se pronašao najmanji mogući broj kovanica koje možemo koristiti.
• Ako vrijednost na bilo kojem niz [i-k] + 1 je manja od postojeće vrijednosti na niz [i], vrijednost zamijenite na niz [i] s onim na niz [i-k] +1.

Kodirati

def coin_change (d, iznos, k):
brojevi = [0] * (iznos + 1)
za j u rasponu (1, iznos + 1):
minimum = iznos
za i u rasponu (1, k + 1):
ako je (j> = d [i]):
minimum = min (najmanje, 1 + brojevi [j-d [i]])
brojevi [j] = minimum
povratni brojevi [iznos]

3. Fibonacci

Izjava o problemu

Fibonaccijev niz je niz cijelih brojeva gdje je sljedeći cijeli broj u nizu zbroj prethodna dva.

Definiran je sljedećom rekurzivnom relacijom: F (0) = 0, F (n) = F (n-1) + F (n-2), gdje Ž (n) je n^th termin. U ovom problemu moramo generirati sve brojeve u Fibonaccijevom nizu do zadanog n^th termin.

Algoritam

• Prvo upotrijebite rekurzivni pristup da biste implementirali zadati odnos ponavljanja.
• Rekurzivno rješavanje ovog problema podrazumijeva slom Ž (n) u F (n-1) + F (n-2), a zatim pozivanje funkcije pomoću Ž (n-1) i Ž (n + 2) kao parametri. To radimo do osnovnih slučajeva kada n = 0, ili n = 1 su dosegnuti.
• Sada koristimo tehniku ​​koja se naziva pamćenje. Pohranite rezultate svih poziva funkcija u niz. To će osigurati da za svaki n, Ž (n) treba izračunati samo jednom.
• Za bilo koji sljedeći izračun, njegova se vrijednost može jednostavno dobiti iz niza u konstantnom vremenu.

Kodirati

def fibonacci (n): 
fibNums = [0, 1] 
za i u rasponu (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
vrati fibNums [n] 

4. Najduže sve veće slijedeće

Izjava o problemu

Pronađite duljinu najveće narastuće podsekcije unutar datog niza. Najduža rastuća podsljednost je podrednost unutar niza brojeva s rastućim redoslijedom. Brojevi unutar podredbe moraju biti jedinstveni i rastućim redoslijedom.

Također, stavke niza ne trebaju biti uzastopne.

Algoritam

• Započnite s rekurzivnim pristupom gdje računate vrijednost najdulje narastuće podsljedice svaki mogući podniz od indeksa nula do indeksa i, gdje je i manja ili jednaka veličini niz.
• Da biste ovu metodu pretvorili u dinamičku, stvorite niz za pohranu vrijednosti za svaku podsekvencu. Inicijalizirajte sve vrijednosti ovog polja na 0.
• Svaki indeks ja ovog niza odgovara duljini najdulje narastuće podsljedice za podniz veličine ja.
• Sada, za svaki rekurzivni poziv od findLIS (arr, n), provjeri n^th indeks niza. Ako je ova vrijednost 0, izračunajte vrijednost pomoću metode u prvom koraku i pohranite je na n^th indeks.
• Konačno, vratite maksimalnu vrijednost iz polja. Ovo je duljina najdulje narastuće podsljedice dane veličine n.

Kodirati

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
za i u rasponu (1, n):
za j u rasponu (0, i):
ako su myArray [i]> myArray [j] i lis [i] lis [i] = lis [j] +1
maxVal = 0
za i u rasponu (n):
maxVal = max (maxVal, lis [i])
povrat maxVal

Rješenja za probleme dinamičkog programiranja

Sad kad ste prošli neke od najpopularnijih problema s dinamičkim programiranjem, vrijeme je da sami pokušate implementirati rješenja. Ako ste zapeli, uvijek se možete vratiti i uputiti se na odjeljak algoritma za svaki gore navedeni problem.

S obzirom na to koliko su tehnike poput rekurzije i dinamičkog programiranja danas popularne, neće biti štetno provjeriti neke popularne platforme na kojima možete naučiti takve koncepte i usavršite svoje kodiranje. Iako se možda nećete svakodnevno susretati s tim problemima, sigurno ćete ih susresti u tehničkom razgovoru.

Naravno, posjedovanje znanja o uobičajenim problemima sigurno će vam isplatiti dividendu kada odete na sljedeći razgovor. Pa otvori svoj omiljeni IDE, i započnite!

9 najboljih YouTube kanala s programskim kodom za učenje programiranja

Jeste li spremni za kodiranje? Ovi YouTube kanali izvrstan su način za početak razvoja igara, aplikacija, weba i drugog.

O autoru