Dynamické programování: příklady, běžné problémy a řešení

Není pochyb o tom, že problémy s dynamickým programováním mohou být v kódovacím rozhovoru velmi zastrašující. I když možná víte, že je třeba problém vyřešit pomocí metody dynamického programování, je obtížné přijít s fungujícím řešením v omezeném časovém rámci.

Nejlepší způsob, jak být dobrý v problémech s dynamickým programováním, je projít jich tolik, kolik můžete. I když si nemusíte nutně pamatovat řešení každého problému, je dobré mít představu, jak tento problém implementovat.

Co je dynamické programování?

Jednoduše řečeno, dynamické programování je optimalizační metoda pro rekurzivní algoritmy, z nichž většina se používá k řešení výpočetních nebo matematických problémů.

Můžete jej také nazvat algoritmickou technikou řešení optimalizačního problému rozdělením na jednodušší dílčí problémy. Klíčovým principem, na kterém je založeno dynamické programování, je to, že optimální řešení problému závisí na řešení jeho dílčích problémů.

Kdekoli vidíme rekurzivní řešení, které má opakované volání stejných vstupů, můžeme jej optimalizovat pomocí dynamického programování. Myšlenkou je jednoduše uložit výsledky dílčích problémů, abychom je nemuseli přepočítávat, když je to později potřeba.

Dynamicky programovaná řešení mají polynomiální složitost, která zajišťuje mnohem rychlejší dobu chodu než jiné techniky, jako je rekurze nebo zpětné sledování. Ve většině případů dynamické programování snižuje časovou složitost, známou také jako velký-O, od exponenciálního po polynomiální.

Co je Big-O notace?

Váš kód musí být efektivní, ale jak ukážete, jak efektivní je něco? S Big-O!

Nyní, když máte dobrou představu o tom, co je dynamické programování, je čas vyzkoušet několik běžných problémů a jejich řešení.

Problémy s dynamickým programováním

1. Problém s batohem

Problémové prohlášení

Vzhledem k sadě položek, z nichž každá má váhu a hodnotu, určete počet jednotlivých položek, které mají být zahrnuty do sběr tak, aby celková hmotnost nepřekročila daný limit a celková hodnota byla tak velká jako možný.

Dostali jste dvě celočíselná pole hodnoty [0..n-1] a váhy [0..n-1] které představují hodnoty a váhy spojené s n položkami. Uvádí se také celé číslo Ž což představuje kapacitu batohu.

Zde řešíme problém s batohem 0/1, což znamená, že se můžeme rozhodnout buď přidat položku, nebo ji vyloučit.

Algoritmus

• Vytvořte dvourozměrné pole pomocí n + 1 řádky a w + 1 sloupce. Číslo řádku n označuje sadu položek od 1 do ia číslo sloupce w označuje maximální nosnost vaku.
• Číselná hodnota v [i] [j] označuje celkovou hodnotu položek až do i v tašce, která unese maximální hmotnost j.
• Na každé souřadnici [i] [j] v poli vyberte maximální hodnotu, bez které můžeme získat položka inebo maximální hodnota, kterou můžeme získat položka ipodle toho, co je větší.
• Maximální dosažitelná hodnota zahrnutím položky i je součtem položky i sám o sobě a maximální hodnotu, kterou lze získat se zbývající kapacitou batohu.
• Proveďte tento krok, dokud nenajdete maximální hodnotu pro Ž^th řádek.

Kód

def FindMax (W, n, hodnoty, váhy):
MaxVals = [[0 pro x v rozsahu (W + 1)] pro x v rozsahu (n + 1)]
pro i v rozsahu (n + 1):
pro w v rozsahu (W + 1):
pokud i == 0 nebo w == 0:
MaxVals [i] [w] = 0
elif váhy [i-1] <= w:
MaxVals [i] [w] = max (hodnoty [i-1]
+ MaxVals [i-1] [w-weights [i-1]], 
MaxVals [i-1] [w])
jiný:
MaxVals [i] [w] = MaxVals [i-1] [w]
návrat MaxVals [n] [W]

2. Problém se změnou mince

Problémové prohlášení

Předpokládejme, že máte řadu čísel, která představují hodnoty každé mince. Vzhledem k konkrétní částce najděte minimální počet mincí, které jsou potřebné k výrobě této částky.

Algoritmus

• Inicializujte pole velikosti n + 1, kde n je částka. Inicializujte hodnotu každého indexu i v poli se rovná částce. To označuje maximální počet mincí (s použitím mincí nominální hodnoty 1) potřebných k vytvoření této částky.
• Protože pro 0 neexistuje žádná nominální hodnota, inicializujte základní případ kde pole [0] = 0.
• Pro každý další index i, porovnáme v něm hodnotu (která je původně nastavena na n + 1) s hodnotou pole [i-k] +1, kde k je méně než i. Tím se v podstatě zkontroluje celé pole až do i-1, aby se zjistil minimální možný počet mincí, které můžeme použít.
• Pokud hodnota vůbec pole [i-k] + 1 je menší než stávající hodnota v pole [i], nahraďte hodnotu na pole [i] s jedním v pole [i-k] +1.

Kód

def coin_change (d, částka, k):
čísla = [0] * (částka + 1)
pro j v rozsahu (1, částka + 1):
minimum = částka
pro i v rozsahu (1, k + 1):
if (j> = d [i]):
minimum = min (minimum, 1 + čísla [j-d [i]])
počty [j] = minimum
návratová čísla [částka]

3. Fibonacci

Problémové prohlášení

Fibonacciho řada je posloupnost celých čísel, kde další celé číslo v řadě je součtem předchozích dvou.

Je definován následujícím rekurzivním vztahem: F (0) = 0, F (n) = F (n-1) + F (n-2), kde F (n) je n^th období. V tomto problému musíme vygenerovat všechna čísla ve Fibonacciho sekvenci až do daného n^th období.

Algoritmus

• Nejprve použijte rekurzivní přístup k implementaci dané relace opakování.
• Rekurzivní řešení tohoto problému znamená rozbití F (n) do F (n-1) + F (n-2)a poté volání funkce pomocí F (n-1) a F (n + 2) jako parametry. Děláme to až do základních případů, kdy n = 0nebo n = 1 jsou dosaženy.
• Nyní používáme techniku ​​zvanou memoizace. Uložte výsledky všech volání funkcí do pole. Tím zajistíte, že pro každé n, F (n) je třeba vypočítat pouze jednou.
• Pro jakékoli následné výpočty lze jeho hodnotu jednoduše načíst z pole v konstantním čase.

Kód

def fibonacci (n): 
fibNums = [0, 1] 
pro i v rozsahu (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
vrátit fibNums [n] 

4. Nejdelší rostoucí posloupnost

Problémové prohlášení

Najděte délku nejdelší rostoucí posloupnosti uvnitř daného pole. Nejdelší rostoucí subsekvence je subsekvence v poli čísel s rostoucím pořadím. Čísla v subsekvenci musí být jedinečná a vzestupně.

Položky sekvence také nemusí být po sobě jdoucí.

Algoritmus

• Začněte s rekurzivním přístupem, kde vypočítáte hodnotu nejdelší rostoucí posloupnosti všechny možné podskupiny od indexu nula po index i, kde i je menší nebo rovný velikosti pole.
• Chcete-li tuto metodu změnit na dynamickou, vytvořte pole pro uložení hodnoty pro každou posloupnost. Inicializujte všechny hodnoty tohoto pole na 0.
• Každý index i tohoto pole odpovídá délce nejdelší rostoucí subsekvence pro podskupinu velikosti i.
• Nyní pro každé rekurzivní volání findLIS (arr, n), zkontrolovat n^th index pole. Pokud je tato hodnota 0, vypočítejte hodnotu pomocí metody v prvním kroku a uložte ji na n^th index.
• Nakonec vraťte maximální hodnotu z pole. Toto je délka nejdelší rostoucí posloupnosti dané velikosti n.

Kód

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

Řešení problémů s dynamickým programováním

Nyní, když jste prošli některými z nejpopulárnějších problémů s dynamickým programováním, je čas zkusit implementovat řešení sami. Pokud jste zaseknutí, můžete se kdykoli vrátit a podívat se do sekce algoritmů pro každý výše uvedený problém.

Vzhledem k tomu, jaké jsou dnes populární techniky, jako je rekurze a dynamické programování, by nebylo na škodu podívat se na některé populární platformy, kde se můžete takové koncepty naučit a zdokonalte své kódovací schopnosti. I když se s těmito problémy nemusíte setkávat každý den, určitě se s nimi setkáte na technickém pohovoru.

Přirozeně, mít know-how o běžných problémech je povinno vyplatit dividendy, když půjdete na další pohovor. Takže otevřete svůj oblíbené IDEa začněte!

9 nejlepších kódových kanálů YouTube pro učení programování

Jste připraveni zahájit programování? Tyto kanály YouTube jsou skvělým způsobem, jak začít s vývojem her, aplikací, webu a dalších.

O autorovi