Dynaaminen ohjelmointi: Esimerkkejä, yleisiä ongelmia ja ratkaisuja

Ei ole epäilystäkään siitä, että dynaamiset ohjelmointiongelmat voivat olla hyvin pelottavia koodaushaastattelussa. Vaikka tiedätkin, että ongelma on ratkaistava dynaamisella ohjelmointimenetelmällä, on haaste pystyä keksimään toimiva ratkaisu rajoitetussa ajassa.

Paras tapa olla hyvä dynaamisissa ohjelmointiongelmissa on käydä läpi niin monta kuin mahdollista. Vaikka sinun ei välttämättä tarvitse muistaa jokaisen ongelman ratkaisua, on hyvä olla käsitys siitä, miten se toteutetaan.

Mikä on dynaaminen ohjelmointi?

Yksinkertaisesti sanottuna dynaaminen ohjelmointi on optimointimenetelmä rekursiivisille algoritmeille, joista suurinta osaa käytetään laskenta- tai matemaattisten ongelmien ratkaisemiseen.

Voit myös kutsua sitä algoritmiseksi tekniikaksi optimointiongelman ratkaisemiseksi jakamalla se yksinkertaisempiin alaongelmiin. Dynaamisen ohjelmoinnin keskeinen periaate on, että ongelman optimaalinen ratkaisu riippuu sen alaongelmien ratkaisuista.

Aina kun näemme rekursiivisen ratkaisun, jolla on toistuvia kutsuja samoille tuloille, voimme optimoida sen dynaamisen ohjelmoinnin avulla. Ajatuksena on yksinkertaisesti tallentaa osaongelmien tulokset, jotta meidän ei tarvitse laskea niitä uudelleen tarvittaessa myöhemmin.

Dynaamisesti ohjelmoiduilla ratkaisuilla on polynomi monimutkaisuus, joka takaa paljon nopeamman ajoajan kuin muut tekniikat, kuten rekursio tai takaisku. Useimmissa tapauksissa dynaaminen ohjelmointi vähentää ajan monimutkaisuutta, joka tunnetaan myös nimellä iso-O, eksponentiaalisesta polynomiin.

Mikä on Big-O-merkintä?

Koodisi on oltava tehokas, mutta miten osoitat, kuinka tehokas jokin on? Big-O: n kanssa!

Nyt kun sinulla on hyvä käsitys dynaamisesta ohjelmoinnista, on aika tarkistaa muutama yleinen ongelma ja niiden ratkaisut.

Dynaamiset ohjelmointiongelmat

1. Selkäreppuongelma

Ongelma

Kun otetaan huomioon joukko kohteita, joista jokaisella on paino ja arvo, määritä jokaisen a-kohtaan sisällytettävän kohteen numero kokoelma niin, että kokonaispaino ei ylitä tiettyä rajaa ja kokonaisarvo on yhtä suuri kuin mahdollista.

Sinulle annetaan kaksi kokonaislukumatriisia arvot [0..n-1] ja painot [0..n-1] jotka edustavat vastaavasti n kohteeseen liittyviä arvoja ja painoja. Annetaan myös kokonaisluku W mikä edustaa repun kapasiteettia.

Tässä ratkaisemme 0/1 -reppuongelman, mikä tarkoittaa, että voimme joko lisätä kohteen tai sulkea sen pois.

Algoritmi

• Luo kaksiulotteinen taulukko n + 1 rivit ja w + 1 sarakkeita. Rivinumero n tarkoittaa alkioiden joukkoa 1 - ija sarakkeen numero w tarkoittaa pussin suurinta kantokykyä.
• Numeerinen arvo kohdassa [i] [j] tarkoittaa tuotteiden kokonaisarvoa vuoteen i pussissa, johon mahtuu enimmäispaino j.
• Jokaisella koordinaatilla [i] [j] valitse taulukosta suurin arvo, jonka voimme saada ilman nimike itai suurin arvo, jonka voimme saada nimike ikumpi on suurempi.
• Suurin saavutettavissa oleva arvo sisällyttämällä kohde i on erän summa i itse ja suurin arvo, joka voidaan saavuttaa repun jäljellä olevalla kapasiteetilla.
• Suorita tämä vaihe, kunnes löydät arvon enimmäisarvon W^th rivi.

Koodi

def FindMax (W, n, arvot, painot):
MaxVals = [[0 x: lle alueella (W + 1)] x: lle alueella (n + 1)]
i: lle alueella (n + 1):
w alueella (W + 1):
jos i == 0 tai w == 0:
MaxVals [i] [w] = 0
elif-painot [i-1] <= w:
MaxVals [i] [w] = max (arvot [i-1]
+ MaxVals [i-1] [w-painot [i-1]], 
MaxVals [i-1] [w])
muu:
MaxVals [i] [w] = MaxVals [i-1] [w]
palauta MaxVals [n] [W]

2. Kolikonvaihto-ongelma

Ongelma

Oletetaan, että sinulle annetaan joukko numeroita, jotka edustavat kunkin kolikon arvoja. Kun otetaan huomioon tietty määrä, etsi vähimmäismäärä kolikoita, joita tarvitaan kyseisen määrän tuottamiseen.

Algoritmi

• Alusta kokoinen taulukko n + 1, jossa n on summa. Alusta jokaisen indeksin arvo i taulukossa olevan määrän kanssa. Tämä tarkoittaa kolikoiden enimmäismäärää (käyttäen 1-nimisiä kolikoita), joka tarvitaan kyseisen määrän muodostamiseen.
• Koska 0: lle ei ole nimellisarvoa, alusta perustapaus missä taulukko [0] = 0.
• Jokaiselle muulle indeksille i, verrataan siinä olevaa arvoa (joka on alun perin asetettu arvoon n + 1) arvon kanssa taulukko [i-k] +1, missä k on vähemmän kuin i. Tämä tarkistaa olennaisesti koko taulukon i-1: een saakka löytääksesi mahdollisimman pienen mahdollisen kolikoiden määrän.
• Jos arvo missä tahansa taulukko [i-k] + 1 on pienempi kuin nykyinen arvo taulukko [i], korvaa arvo kohdassa taulukko [i] kanssa taulukko [i-k] +1.

Koodi

def kolikonvaihto (d, määrä, k):
numerot = [0] * (summa + 1)
j: lle alueella (1, määrä + 1):
minimi = määrä
i: lle alueella (1, k + 1):
jos (j> = d [i]):
minimi = min (minimi, 1 + numerot [j-d [i]])
numerot [j] = vähimmäismäärä
palautusnumerot [määrä]

3. Fibonacci

Ongelma

Fibonacci-sarja on kokonaislukujen sarja, jossa sarjan seuraava kokonaisluku on kahden edellisen summa.

Sen määrittelee seuraava rekursiivinen suhde: F (0) = 0, F (n) = F (n-1) + F (n-2), missä F (n) on sitten^th termi. Tässä tehtävässä meidän on luotava kaikki numerot Fibonacci-sekvenssissä tiettyyn n: ään asti^th termi.

Algoritmi

• Käytä ensin rekursiivista lähestymistapaa annetun toistosuhteen toteuttamiseen.
• Tämän ongelman rekursiivinen ratkaiseminen edellyttää hajoamista F (n) osaksi F (n-1) + F (n-2)ja kutsumalla sitten toiminto painikkeella F (n-1) ja F (n + 2) parametreina. Teemme tämän, kunnes perustapaukset missä n = 0tai n = 1 saavutetaan.
• Nyt käytämme tekniikkaa, jota kutsutaan muistiinpanoksi. Tallenna kaikkien toimintokutsujen tulokset taulukkoon. Tämä varmistaa, että jokaista n F (n) tarvitsee laskea vain kerran.
• Mahdollisissa myöhemmissä laskelmissa sen arvo voidaan yksinkertaisesti hakea matriisista vakiona.

Koodi

def fibonacci (n): 
fibNums = [0, 1] 
i: lle alueella (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
palauta fibNums [n] 

4. Pisin kasvava seuraus

Ongelma

Etsi pisimmän kasvavan jakson pituus tietyn taulukon sisällä. Pisin kasvava osajoukko on osajoukko kasvavassa järjestyksessä. Jakson sisällä olevien numeroiden on oltava yksilöllisiä ja nousevassa järjestyksessä.

Sekvenssin kohteiden ei myöskään tarvitse olla peräkkäisiä.

Algoritmi

• Aloita rekursiivisella lähestymistavalla, jossa lasketaan pisin pituuden kasvavan osuuden arvo jokainen mahdollinen osa-alue indeksistä nollasta indeksiin i, jossa i on pienempi tai yhtä suuri kuin taulukko.
• Jos haluat muuttaa tämän menetelmän dynaamiseksi, luo taulukko, joka tallentaa arvon jokaiselle osalle. Alusta tämän taulukon kaikki arvot arvoon 0.
• Jokainen hakemisto i Tämän taulukon pituus vastaa pisimmän kasvavan osajohdon kokoa i.
• Nyt jokaisesta rekursiivisesta puhelusta findLIS (arr, n), Tarkista n^th taulukon indeksi. Jos tämä arvo on 0, laske sitten arvo ensimmäisen vaiheen menetelmällä ja tallenna se kohtaan n^th indeksi.
• Palauta lopuksi taulukon maksimiarvo. Tämä on tietyn koon pisimmän kasvavan jakson pituus n.

Koodi

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
i: lle alueella (1, n):
j: lle alueella (0, i):
jos myArray [i]> myArray [j] ja lis [i] lis [i] = lis [j] +1
maxVal = 0
i: lle alueella (n):
maxVal = max (maxVal, lis [i])
palaa maxVal

Dynaamisten ohjelmointiongelmien ratkaisut

Nyt kun olet käynyt läpi suosituimpia dynaamisia ohjelmointiongelmia, on aika yrittää toteuttaa ratkaisut itse. Jos olet jumissa, voit aina palata takaisin ja katsoa kunkin yllä olevan ongelman algoritmi-osion.

Kun otetaan huomioon, kuinka suosittuja tekniikoita, kuten rekursio ja dynaaminen ohjelmointi ovat nykyään, ei ole haittaa tarkistaa joitain suosittuja alustoja, joissa voit oppia tällaisia ​​käsitteitä ja hioa koodaustaitojasi. Vaikka et välttämättä kohtaisi näitä ongelmia päivittäin, kohtaat varmasti ne teknisessä haastattelussa.

Luonnollisesti yhteisten ongelmien taitotiedon saaminen maksaa osinkoja, kun menet seuraavaan haastatteluun. Joten avaa suosikki IDEja aloita!

9 parasta koodikoodattua YouTube-kanavaa ohjelmoinnin oppimiseksi

Oletko valmis aloittamaan koodauksen? Nämä YouTube-kanavat ovat loistava tapa aloittaa pelien, sovellusten, verkkojen ja muun kehityksen aloittaminen.

Kirjailijasta