Dünaamiline programmeerimine: näited, levinumad probleemid ja lahendused

Pole kahtlust, et dünaamilised programmeerimisprobleemid võivad kodeerimisintervjuus väga hirmutada. Isegi kui võite teada, et probleem tuleb lahendada dünaamilise programmeerimismeetodi abil, on väljakutse, kui suudate piiratud aja jooksul pakkuda toimivat lahendust.

Parim viis dünaamiliste programmeerimisprobleemide lahendamiseks on läbida nii palju kui võimalik. Kuigi te ei pea tingimata iga probleemi lahendust meelde jätma, on hea, kui teil on idee selle rakendamise jätkamiseks.

Mis on dünaamiline programmeerimine?

Lihtsamalt öeldes on dünaamiline programmeerimine rekursiivsete algoritmide optimeerimismeetod, millest enamikku kasutatakse arvutus- või matemaatiliste probleemide lahendamiseks.

Võite seda nimetada ka optimeerimisprobleemi lahendamise algoritmiliseks tehnikaks, jagades selle lihtsamateks alamprobleemideks. Dünaamilise programmeerimise põhiprintsiip on see, et probleemi optimaalne lahendus sõltub selle alamprobleemide lahendustest.

Kõikjal, kus näeme rekursiivset lahendust, millel on korduvad üleskutsed samadele sisenditele, saame selle dünaamilise programmeerimise abil optimeerida. Idee on alamprobleemide tulemused lihtsalt salvestada, nii et me ei peaks neid hiljem vajadusel ümber arvutama.

Dünaamiliselt programmeeritud lahendustel on polünoomide keerukus, mis tagab palju kiirema tööaja kui muud tehnikad, näiteks rekursioon või tagasitee. Enamasti vähendab dünaamiline programmeerimine aja keerukust, tuntud ka kui suur-O, eksponentsiaalsest polünoomini.

Mis on Big-O tähistamine?

Teie kood peab olema tõhus, kuid kuidas näidata, kui midagi tõhusat on? Big-O-ga!

Nüüd, kui teil on hea ettekujutus sellest, mis on dünaamiline programmeerimine, on aeg vaadata üle mõned levinumad probleemid ja nende lahendused.

Dünaamilise programmeerimise probleemid

1. Seljakotiprobleem

Probleemipüstituses

Võttes arvesse üksuste komplekti, millest igaühel on kaal ja väärtus, määrake iga a-sse lisatava üksuse arv kogumass, nii et kogumass ei ületa etteantud piiri ja koguväärtus on sama suur kui võimalik.

Teile antakse kaks täisarvu massiivi väärtused [0..n-1] ja kaalud [0..n-1] mis tähistavad vastavalt n üksusega seotud väärtusi ja kaalu. Samuti on antud täisarv W mis tähistab seljakoti mahtu.

Siin lahendame seljakoti 0/1 probleemi, mis tähendab, et saame valida kas üksuse lisamise või välistamise.

Algoritm

• Looge kahemõõtmeline massiiv koos n + 1 read ja w + 1 veerud. Rea number n tähistab üksuste kogumit vahemikus 1 kuni ija veeru number w tähistab koti maksimaalset kandevõimet.
• Numbriline väärtus [i] [j] tähistab esemete koguväärtust kuni i kotis, mis mahutab maksimaalset raskust j.
• Igal koordinaadil [i] [j] valige massiivist maksimaalne väärtus, mille saame ilma punkt ivõi maksimaalne väärtus, mille saame saada punkt ikumb on suurem.
• Maksimaalne saadav väärtus punkti i lisamise teel on üksuse summa i ise ja maksimaalne väärtus, mis on võimalik seljakoti järelejäänud mahuga.
• Tehke seda sammu, kuni leiate väärtuse maksimaalse väärtuse W^th rida.

Kood

def FindMax (W, n, väärtused, kaalud):
MaxVals = [[0 x vahemikus (W + 1)] x vahemikus (n + 1)]
i jaoks vahemikus (n + 1):
w vahemikus (W + 1):
kui i == 0 või w == 0:
MaxVals [i] [w] = 0
elifi kaal [i-1] <= w:
MaxVals [i] [w] = max (väärtused [i-1]
+ MaxVals [i-1] [w-kaalud [i-1]], 
MaxVals [i-1] [w])
muu:
MaxVals [i] [w] = MaxVals [i-1] [w]
tagastage MaxVals [n] [W]

2. Müntide vahetamise probleem

Probleemipüstituses

Oletame, et teile on antud hulga numbreid, mis tähistavad iga mündi väärtusi. Konkreetse summa korral leidke miinimumarv münte, mida selle summa saamiseks vaja läheb.

Algoritm

• Initsialiseeri massiivi suurus n + 1, kus n on summa. Initsialiseeri iga indeksi väärtus i massiivis võrdub summa. See tähistab maksimaalset müntide arvu (kasutades nimiväärtusega 1 münte), mis on vajalik selle summa moodustamiseks.
• Kuna 0 jaoks pole nimiväärtust, lähtestage lähtetäht kus massiiv [0] = 0.
• Iga teise indeksi jaoks i, võrdleme selles olevat väärtust (mis on algselt seatud väärtusele n + 1) väärtusega massiiv [i-k] +1, kus k on vähem kui i. See kontrollib sisuliselt kogu massiivi kuni i-1-ni, et leida võimalikult väike müntide arv, mida saame kasutada.
• Kui väärtus on ükskõik milline massiiv [i-k] + 1 on väiksem kui praegune väärtus massiiv [i], asendage väärtus väärtusega massiiv [i] kellega massiiv [i-k] +1.

Kood

def mündivahetus (d, summa, k):
numbrid = [0] * (summa + 1)
j jaoks vahemikus (1, summa + 1):
miinimum = summa
i jaoks vahemikus (1, k + 1):
kui (j> = d [i]):
miinimum = min (miinimum, 1 + arv [j-d [i]])
arvud [j] = miinimum
tagastusnumbrid [summa]

3. Fibonacci

Probleemipüstituses

Fibonacci seeria on täisarvude jada, kus seeria järgmine täisarv on kahe eelmise summa.

Selle määratleb järgmine rekursiivne seos: F (0) = 0, F (n) = F (n-1) + F (n-2), kus F (n) on n^th tähtaeg. Selles ülesandes peame genereerima kõik arvud Fibonacci järjestuses kuni antud n-ni^th tähtaeg.

Algoritm

• Esiteks kasutage antud korduvussuhte rakendamiseks rekursiivset lähenemist.
• Selle probleemi rekursiivne lahendamine tähendab purunemist F (n) sisse F (n-1) + F (n-2)ja seejärel funktsiooni kutsumine klahviga F (n-1) ja F (n + 2) parameetritena. Teeme seda kuni põhijuhtumini, kus n = 0või n = 1 on jõutud.
• Nüüd kasutame tehnikat, mida nimetatakse memodeks. Kõigi funktsioonikõnede tulemused salvestatakse massiivi. See tagab, et iga n F (n) tuleb arvutada ainult üks kord.
• Mis tahes järgnevate arvutuste jaoks saab selle väärtuse massiivist lihtsalt konstantse ajaga hankida.

Kood

def fibonacci (n): 
fibNums = [0, 1] 
i jaoks vahemikus (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
tagastama fibNums [n] 

4. Kõige kauem kasvav tagajärg

Probleemipüstituses

Leidke antud massiivi sees pikima kasvava järjestuse pikkus. Kõige pikem järjest suurenev järjestus on järjestus arvude massiivi sees. Järjekorra numbrid peavad olema kordumatud ja kasvavas järjekorras.

Samuti ei pea järjestuse üksused olema järjestikused.

Algoritm

• Alustage rekursiivsest lähenemisviisist, kus arvutate kõige pikema kasvava järjestuse väärtuse kõik võimalikud alamkaardid indeksist nullini indeksini i, kus i on väiksem kui või võrdne väärtuse suurusega massiiv.
• Selle meetodi muutmiseks dünaamiliseks looge massiiv iga järgneva väärtuse salvestamiseks. Initsialiseeri selle massiivi kõik väärtused väärtuseks 0.
• Iga indeks i selle massiivi suurus vastab vastava suurusega alarea kõige kauem kasvava järjestuse pikkusele i.
• Nüüd iga rekursiivse kõne korral findLIS (arr, n), kontrolli n^th massiivi indeks. Kui see väärtus on 0, arvutage väärtus, kasutades esimese sammu meetodit, ja salvestage see väärtusele n^th indeks.
• Lõpuks tagastage massiivi maksimaalne väärtus. See on antud suuruse kõige pikema kasvava järjestuse pikkus n.

Kood

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
i jaoks vahemikus (1, n):
j jaoks vahemikus (0, i):
kui myArray [i]> myArray [j] ja lis [i] lis [i] = lis [j] +1
maxVal = 0
i jaoks vahemikus (n):
maxVal = max (maxVal, lis [i])
tagastage maxVal

Dünaamiliste programmeerimisprobleemide lahendused

Nüüd, kui olete läbinud mõned kõige populaarsemad dünaamilise programmeerimise probleemid, on aeg proovida lahendusi ise rakendada. Kui olete ummikus, võite alati tagasi tulla ja vaadata ülaltoodud probleemide algoritmide jaotist.

Arvestades seda, kui populaarsed tehnikad nagu rekursioon ja dünaamiline programmeerimine täna on, pole valus vaadata mõnda populaarset platvormi, kus saate selliseid mõisteid õppida lihvige oma kodeerimisoskusi. Ehkki te ei pruugi igapäevaselt nende probleemidega kokku puutuda, kohtate neid kindlasti tehnilises intervjuus.

Loomulikult maksab levinud probleemide oskusteabe olemasolu järgmisele intervjuule minnes dividende. Nii et avage oma lemmik IDEja alustage!

9 parimat koodikanaliga YouTube'i kanalit programmeerimise õppimiseks

Kas olete kodeerimise alustamiseks valmis? Need YouTube'i kanalid on suurepärane viis mängu, rakenduse, veebi ja muu arenduse alustamiseks.

Autori kohta