Dynamické programovanie: Príklady, bežné problémy a riešenia

Niet pochýb o tom, že problémy s dynamickým programovaním môžu byť pri kódovacom pohovore veľmi zastrašujúce. Aj keď viete, že je potrebné problém vyriešiť pomocou metódy dynamického programovania, je náročné prísť s funkčným riešením v obmedzenom časovom rámci.

Najlepší spôsob, ako byť v problémoch s dynamickým programovaním dobrý, je prekonať ich čo najviac. Aj keď si nemusíte nevyhnutne pamätať riešenie každého problému, je dobré mať predstavu, ako tento problém implementovať.

Čo je to dynamické programovanie?

Jednoducho povedané, dynamické programovanie je optimalizačná metóda pre rekurzívne algoritmy, ktoré sa väčšinou používajú na riešenie výpočtových alebo matematických úloh.

Môžete ho tiež nazvať algoritmickou technikou riešenia problému s optimalizáciou jeho rozdelením na jednoduchšie čiastkové problémy. Kľúčovým princípom, na ktorom je založené dynamické programovanie, je to, že optimálne riešenie problému závisí od riešení jeho čiastkových problémov.

Kdekoľvek vidíme rekurzívne riešenie, ktoré má opakované volania pre rovnaké vstupy, môžeme ho optimalizovať pomocou dynamického programovania. Cieľom je jednoducho uložiť výsledky čiastkových problémov, aby sme ich nemuseli musieť neskôr prepočítavať.

Dynamicky programované riešenia majú polynomiálnu zložitosť, ktorá zaisťuje oveľa rýchlejší čas chodu ako iné techniky, ako je rekurzia alebo spätné sledovanie. Vo väčšine prípadov dynamické programovanie znižuje časovú zložitosť, známu tiež ako veľký-O, od exponenciálneho po polynomický.

Čo je to Big-O notácia?

Váš kód musí byť efektívny, ale ako ukážete, aké efektívne je niečo? S Big-O!

Teraz, keď máte dobrú predstavu o tom, čo je dynamické programovanie, je čas vyskúšať niekoľko bežných problémov a ich riešení.

Problémy s dynamickým programovaním

1. Problém s batohom

Vyhlásenie o probléme

Na základe množiny položiek, z ktorých každá má váhu a hodnotu, určite počet jednotlivých položiek, ktoré majú byť zahrnuté v a zber, aby celková hmotnosť nepresiahla daný limit a celková hodnota bola rovnako veľká ako možné.

Dostanete dve celé čísla hodnoty [0..n-1] a hmotnosti [0..n-1] ktoré predstavujú hodnoty a váhy spojené s n položkami. Uvádza sa tiež celé číslo Ž čo predstavuje kapacitu batohu.

Tu riešime problém s batohom 0/1, čo znamená, že si môžeme zvoliť, či pridáme položku, alebo ju vylúčime.

Algoritmus

• Vytvorte dvojrozmerné pole pomocou n + 1 riadky a w + 1 stĺpce. Číslo riadku n označuje množinu položiek od 1 do ia číslo stĺpca w označuje maximálnu nosnosť vaku.
• Číselná hodnota pri [i] [j] označuje celkovú hodnotu položiek do i vo vaku, ktorý unesie maximálnu hmotnosť j.
• Na každej súradnici [i] [j] v poli vyberte maximálnu hodnotu, bez ktorej môžeme získať položka ialebo maximálna hodnota, s ktorou môžeme získať položka ipodľa toho, ktorá je väčšia.
• Maximálna dosiahnuteľná hodnota zahrnutím položky i je súčet položky i sám a maximálna hodnota, ktorú je možné získať so zvyšnou kapacitou batohu.
• Vykonajte tento krok, kým nenájdete maximálnu hodnotu pre Ž^th riadok.

Zákonníka

def FindMax (W, n, hodnoty, váhy):
MaxVals = [[0 pre x v rozsahu (W + 1)] pre x v rozsahu (n + 1)]
pre i v rozsahu (n + 1):
pre w v rozsahu (W + 1):
ak i == 0 alebo w == 0:
MaxVals [i] [w] = 0
elif váhy [i-1] <= š:
MaxVals [i] [w] = max (hodnoty [i-1]
+ MaxVals [i-1] [w-váhy [i-1]], 
MaxVals [i-1] [w])
inak:
MaxVals [i] [w] = MaxVals [i-1] [w]
návrat MaxVals [n] [W]

2. Problém so zmenou mince

Vyhlásenie o probléme

Predpokladajme, že dostanete pole čísel, ktoré predstavujú hodnoty jednotlivých mincí. Pri danom konkrétnom množstve vyhľadajte minimálny počet mincí, ktoré sú potrebné na výrobu tohto množstva.

Algoritmus

• Inicializujte pole veľkosti n + 1, kde n je suma. Inicializujte hodnotu každého indexu i v poli sa rovná sume. To označuje maximálny počet mincí (s použitím mincí nominálnej hodnoty 1) potrebný na vytvorenie tejto sumy.
• Pretože pre 0 neexistuje žiadna nominálna hodnota, inicializujte základný prípad kde pole [0] = 0.
• Pre každý ďalší index i, porovnáme v ňom hodnotu (ktorá je pôvodne nastavená na n + 1) s hodnotou pole [i-k] +1, kde k je menej než i. Toto v podstate skontroluje celé pole až do i-1, aby sa zistil minimálny možný počet mincí, ktoré môžeme použiť.
• Ak hodnota vôbec pole [i-k] + 1 je nižšia ako súčasná hodnota pri pole [i], nahraďte hodnotu na pole [i] s jedným na pole [i-k] +1.

Zákonníka

def coin_change (d, suma, k):
čísla = [0] * (suma + 1)
pre j v rozsahu (1, suma + 1):
minimum = suma
pre i v rozsahu (1, k + 1):
if (j> = d [i]):
minimum = min (minimum, 1 + čísla [j-d [i]])
počty [j] = minimum
spiatočné čísla [suma]

3. Fibonacci

Vyhlásenie o probléme

Séria Fibonacci je postupnosť celých čísel, kde ďalšie celé číslo v rade je súčtom predchádzajúcich dvoch.

Je to definované nasledujúcim rekurzívnym vzťahom: F (0) = 0, F (n) = F (n-1) + F (n-2), kde F (n) je n^th termín. V tomto probléme musíme vygenerovať všetky čísla vo Fibonacciho postupnosti až do daného n^th termín.

Algoritmus

• Najskôr pomocou rekurzívneho prístupu implementujte daný vzťah opakovania.
• Rekurzívne riešenie tohto problému znamená prelomenie F (n) do F (n-1) + F (n-2)a potom volanie funkcie pomocou F (n-1) a F (n + 2) ako parametre. Robíme to až do základných prípadov, keď n = 0alebo n = 1 sú dosiahnuté.
• Teraz používame techniku ​​zvanú memoizácia. Výsledky všetkých volaní funkcií sa ukladajú do poľa. To zabezpečí, že za každých n, F (n) je potrebné vypočítať iba raz.
• Pre akékoľvek ďalšie výpočty možno jeho hodnotu jednoducho načítať z poľa v konštantnom čase.

Zákonníka

def fibonacci (n): 
fibNums = [0, 1] 
pre i v rozsahu (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
návratové čísla fibNums [n] 

4. Najdlhšie rastúca následnosť

Vyhlásenie o probléme

Nájdite dĺžku najdlhšej rastúcej subsekvencie vo vnútri daného poľa. Najdlhšia rastúca subsekvencia je subsekvencia v rade čísel s rastúcim poradím. Čísla v podsekvencii musia byť jedinečné a vzostupne.

Položky sekvencie tiež nemusia byť nasledujúce.

Algoritmus

• Začnite rekurzívnym prístupom, pri ktorom vypočítate hodnotu najdlhšie rastúcej podsekvencie každé možné čiastkové pole od indexu nula po index i, kde i je menšia alebo rovnaká ako veľkosť súboru pole.
• Ak chcete túto metódu zmeniť na dynamickú, vytvorte pole na uloženie hodnoty pre každú podsekvenciu. Inicializujte všetky hodnoty tohto poľa na 0.
• Každý index i tohto poľa zodpovedá dĺžke najdlhšie rastúcej subsekvencie pre čiastkové pole veľkosti i.
• Teraz pre každé rekurzívne volanie findLIS (arr, n), skontrolovať n^th index poľa. Ak je táto hodnota 0, potom hodnotu vypočítajte pomocou metódy v prvom kroku a uložte ju na n^th index.
• Nakoniec vráťte maximálnu hodnotu z poľa. Toto je dĺžka najdlhšie rastúcej subsekvencie danej veľkosti n.

Zákonníka

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
pre i v rozsahu (1, n):
pre j v rozsahu (0, i):
ak myArray [i]> myArray [j] a lis [i] lis [i] = lis [j] +1
maxVal = 0
pre i v rozsahu (n):
maxVal = max (maxVal, lis [i])
návrat maxVal

Riešenie problémov s dynamickým programovaním

Teraz, keď ste si prešli niektorými z najpopulárnejších problémov s dynamickým programovaním, je čas vyskúšať si implementovať riešenia sami. Ak ste uviaznutí, môžete sa kedykoľvek vrátiť a pozrieť si sekciu algoritmov pre jednotlivé problémy vyššie.

Vzhľadom na to, aké populárne sú dnes techniky ako rekurzia a dynamické programovanie, nebude na škodu vyskúšať si niektoré populárne platformy, kde sa môžete tieto koncepty naučiť a zdokonaľte svoje kódovacie schopnosti. Aj keď sa s týmito problémami nemusíte stretnúť každý deň, určite sa s nimi stretnete na technickom pohovore.

Prirodzene, mať know-how v oblasti bežných problémov bude určite platiť dividendy, keď sa chystáte na ďalší pohovor. Takže otvorte svoje obľúbené IDE, a začnite!

9 najlepších kódových kanálov YouTube, ktoré umožňujú programovanie

Ste pripravení začať programovať? Tieto kanály YouTube sú skvelým spôsobom, ako začať s vývojom hier, aplikácií, webu a ďalších.

O autorovi