Dinaminis programavimas: pavyzdžiai, bendros problemos ir sprendimai

Neabejotina, kad dinaminio programavimo problemos gali būti labai bauginančios kodavimo interviu. Net kai galite žinoti, kad problemą reikia išspręsti taikant dinaminį programavimo metodą, iššūkis yra sugebėti sugalvoti veikiantį sprendimą per ribotą laiką.

Geriausias būdas gerai išmanyti dinaminio programavimo problemas yra patirti kuo daugiau jų. Nors nebūtinai reikia įsiminti kiekvienos problemos sprendimą, gerai, kad turite idėją, kaip ją įgyvendinti.

Kas yra dinaminis programavimas?

Paprasčiau tariant, dinaminis programavimas yra rekursiškų algoritmų optimizavimo metodas, kuris dažniausiai naudojamas sprendžiant skaičiavimo ar matematines problemas.

Taip pat galite tai pavadinti algoritmine metodika, kaip išspręsti optimizavimo problemą, suskaidant ją į paprastesnes subproblemas. Pagrindinis principas, kuriuo grindžiamas dinaminis programavimas, yra tas, kad optimalus problemos sprendimas priklauso nuo jo subproblemų sprendimų.

Kur matome rekursinį sprendimą, kuris pakartotinai reikalauja tų pačių įėjimų, galime jį optimizuoti naudodami dinaminį programavimą. Idėja yra paprasčiausiai išsaugoti papildomų problemų rezultatus, kad vėliau nereikėtų jų perskaičiuoti, kai to reikia.

Dinamiškai suprogramuoti sprendimai turi polinomo sudėtingumą, kuris užtikrina daug greitesnį veikimo laiką nei kiti metodai, pvz., Rekursija ar grįžimas atgal. Daugeliu atvejų dinaminis programavimas sumažina laiko sudėtingumą, dar vadinamą didelis-O, nuo eksponentinio iki daugianario.

Kas yra „Big-O“ žymėjimas?

Jūsų kodas turi būti efektyvus, bet kaip parodyti, kaip kažkas yra efektyvus? Su Big-O!

Dabar, kai gerai įsivaizduojate, kas yra dinaminis programavimas, laikas patikrinti kelias dažniausiai pasitaikančias problemas ir jų sprendimus.

Dinaminio programavimo problemos

1. Kuprinės problema

Problemos pareiškimas

Atsižvelgdami į elementų rinkinį, kurių kiekvienas turi svorį ir vertę, nustatykite kiekvieno elemento, kurį norite įtraukti, skaičių surinkimas, kad bendras svoris neviršytų nurodytos ribos, o bendra vertė būtų tokia pat kaip įmanoma.

Jums suteikiami du sveikųjų skaičių masyvai reikšmės [0..n-1] ir svoriai [0..n-1] kurie reiškia reikšmes ir svorį, susijusius su atitinkamai n elementais. Taip pat pateikiamas sveikasis skaičius W kuris atspindi kuprinės talpą.

Čia mes sprendžiame 0/1 kuprinės problemą, o tai reiškia, kad galime pasirinkti pridėti elementą arba jį pašalinti.

Algoritmas

• Sukurkite dvimatį masyvą naudodami n + 1 eilučių ir w + 1 stulpeliai. Eilutės numeris n žymi elementų rinkinį nuo 1 iki iir stulpelio numeris w žymi didžiausią krepšio keliamąją galią.
• Skaitinė reikšmė [i] [j] žymi bendrą daiktų vertę iki i maišelyje, kuriame galima nešti didžiausią j svorį.
• Kiekvienoje koordinatėje [i] [j] masyve pasirinkite didžiausią vertę, kurios galime gauti be i punktas, arba didžiausia vertė, kurią galime gauti i punktaskuris didesnis.
• Didžiausia gaunama vertė, įtraukiant i elementą, yra elemento suma i pati didžiausia vertė, kurią galima gauti su likusia kuprinės talpa.
• Atlikite šį veiksmą, kol rasite maksimalią W^tūkst eilutė.

Kodas

def „FindMax“ (W, n, reikšmės, svoriai):
„MaxVals“ = [[0 už x diapazone (W + 1)] x x diapazone (n + 1)]
i diapazone (n + 1):
w diapazone (W + 1):
jei i == 0 arba w == 0:
„MaxVals“ [i] [w] = 0
elif svoriai [i-1] <= w:
„MaxVals“ [i] [w] = maks. (Reikšmės [i-1]
+ „MaxVals“ [i-1] [svoris [i-1]], 
„MaxVals“ [i-1] [w])
Kitas:
„MaxVals“ [i] [w] = „MaxVals“ [i-1] [w]
grąžinti „MaxVals“ [n] [W]

2. Monetų keitimo problema

Problemos pareiškimas

Tarkime, kad jums suteikta skaičių masyvo, kuris atspindi kiekvienos monetos vertes. Atsižvelgdami į konkrečią sumą, raskite mažiausią skaičių monetų, kurių reikia šiai sumai pagaminti.

Algoritmas

• Inicijuokite dydžio masyvą n + 1, kur n yra suma. Inicializuokite kiekvieno indekso vertę i masyve būti lygus sumai. Tai žymi maksimalų monetų skaičių (naudojant 1 nominalo monetas), kurio reikia šiai sumai sudaryti.
• Kadangi 0 vardo nėra, inicijuokite pagrindinį atvejį, kur masyvas [0] = 0.
• Kiekvienam kitam indeksui i, palyginame jame esančią vertę (kuri iš pradžių nustatyta į n + 1) su verte masyvas [i-k] +1, kur k mažiau nei i. Tai iš esmės patikrina visą masyvą iki i-1, kad surastų mažiausią galimą monetų skaičių, kurį galime naudoti.
• Jei vertė bet kurioje masyvas [i-k] + 1 yra mažesnė už esamą vertę masyvas [i], pakeiskite reikšmę masyvas [i] su tuo, kuris yra masyvas [i-k] +1.

Kodas

def monetos pakeitimas (d, suma, k):
skaičiai = [0] * (suma + 1)
j diapazone (1, suma + 1):
minimalus = suma
i diapazone (1, k + 1):
jei (j> = d [i]):
mažiausias = min (mažiausias, 1 + skaičiai [j-d [i]])
skaičiai [j] = mažiausias
grąžinimo numeriai [suma]

3. Fibonači

Problemos pareiškimas

„Fibonacci“ serija yra sveikųjų skaičių seka, kur kitas eilės skaičius yra ankstesnių dviejų suma.

Tai apibūdina šis rekursinis ryšys: F (0) = 0, F (n) = F (n-1) + F (n-2), kur F (n) yra n^tūkst terminas. Šioje problemoje turime generuoti visus Fibonači sekos skaičius iki nurodyto n^tūkst terminas.

Algoritmas

• Pirma, naudokite rekursyvų metodą, kad įgyvendintumėte nurodytą pasikartojimo santykį.
• Rekursyviai išsprendus šią problemą, reikia suskaidyti F (n) į F (n-1) + F (n-2)ir paskui iškvieskite funkciją naudodami F (n-1) ir F (n + 2) kaip parametrus. Mes tai darome iki pagrindinių atvejų, kai n = 0arba n = 1 pasiekiami.
• Dabar mes naudojame techniką, vadinamą atmintimi. Saugokite visų funkcijų iškvietimų rezultatus masyve. Tai užtikrins, kad kiekvienam n F (n) reikia apskaičiuoti tik vieną kartą.
• Atliekant bet kokius paskesnius skaičiavimus, jo vertę paprasčiausiai galima gauti iš masyvo pastoviu laiku.

Kodas

def fibonači (n): 
fibNums = [0, 1] 
i diapazone (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
grąžinti fibNums [n] 

4. Ilgiausiai didėjanti pasekmė

Problemos pareiškimas

Raskite ilgiausiai didėjančio sekos ilgį duotame masyve. Ilgiausiai didėjanti seka yra seka skaičiaus masyve didėjančia tvarka. Skaičiai po eilės turi būti unikalūs ir didėjimo tvarka.

Be to, sekos elementai neturi būti vienas po kito.

Algoritmas

• Pradėkite nuo rekursinio metodo, kur apskaičiuojate ilgiausiai didėjančio sekos vertę kiekvienas įmanomas poskyris nuo indekso nulio iki indekso i, kur i yra mažesnis arba lygus indekso dydžiui masyvas.
• Norėdami paversti šį metodą dinamišku, sukurkite masyvą, kad išsaugotumėte kiekvieno sekos vertę. Inicijuokite visas šio masyvo reikšmes į 0.
• Kiekvienas indeksas i šios masyvo atitinka ilgiausio didėjančio sekos ilgį, kai matuojamas dydis i.
• Dabar už kiekvieną rekursinį skambutį findLIS (arr, n), Patikrink n^tūkst masyvo indeksas. Jei ši vertė yra 0, tada apskaičiuokite vertę naudodami pirmojo veiksmo metodą ir išsaugokite ją n^tūkst indeksas.
• Galiausiai grąžinkite didžiausią masyvo vertę. Tai ilgiausiai augančio tam tikro dydžio sekos ilgis n.

Kodas

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
i diapazone (1, n):
j diapazone (0, i):
jei myArray [i]> myArray [j] ir lis [i] lis [i] = lis [j] +1
maxVal = 0
i diapazone (n):
maxVal = max (maxVal, lis [i])
grąžinti maxVal

Dinaminio programavimo problemų sprendimai

Dabar, kai patyrėte populiariausias dinaminio programavimo problemas, pats laikas pabandyti įgyvendinti sprendimus. Jei esate užstrigęs, visada galite grįžti ir perskaityti kiekvienos aukščiau pateiktos problemos algoritmo skyrių.

Atsižvelgiant į tai, kokia populiari technika šiandien yra rekursija ir dinaminis programavimas, nepakenks patikrinti kai kurias populiarias platformas, kuriose galite išmokti tokių tobulinti savo kodavimo įgūdžius. Nors jums gali nesusidurti su šiomis problemomis kasdien, jūs tikrai susidursite su jais techniniame interviu.

Natūralu, kad žinodamas apie bendras problemas privalai mokėti dividendus, kai eini į kitą interviu. Taigi atverkite savo mėgstamiausia IDEir pradėk!

9 geriausi „YouTube“ kanalai, naudojantys kodą, kad išmoktų programuoti

Pasirengę pradėti koduoti? Šie „YouTube“ kanalai yra puikus būdas pradėti kurti žaidimus, programas, internetą ir kitus kūrinius.

Apie autorių