Dynamické programovanie je technika riešenia zložitých úloh, ktoré pomáha riešiť problémy, ktoré možno rozdeliť na menšie podproblémy, efektívne.
Pri dynamickom programovaní si rozdelíme problém na menšie podproblémy, ktoré vyriešime raz a uložíme si ich výsledky, aby sme ich nemuseli počítať znova. Teda, pamätáme si riešenia pre menšie problémy a keď ich potrebujeme, jednoducho si ich vyberieme, miesto toho, aby sme ich znovu počítali.
Zlodej sa chystá vykradnúť ulicu plnú domov. Každý dom má určitú hodnotu, ktorú získame vykradnutím. Domy sú zoradené na ulici v jednom rade, ale zlodej nechce vykradnúť dva susedné domy, pretože by to vzbudilo podozrenie.
Našou úlohou je zistiť, akú najväčšiu sumu peňazí môže zlodej ukradnúť, bez toho, aby vykradol dva susediace domy.
Najjednoduchšie riešenie tohto problému by mohlo byť napríklad, že si vygenerujeme všetky podmnožiny domov a následne pre každú z nich zistíme, či neobsahuje dva susedné domy. Ak áno, budeme ju ignorovať. Z ostatných podmnožín si nájdeme takú, ktorej súčet hodnôt je najväčší.
Takto získame riešenie nášho problému v exponenciálnom čase, keďže samotných podmnožín je $2^n$. Priamočiara kontrola susednosti nás bude stáť $O(n)$, takže dokopy časová zložitosť takéhoto riešenia bude $O(2^n n)$.
Ukážeme si, ako za použitia dynamického programovania dosiahneme omnoho efektívnejšie riešenie.
Pri dynamickom programovaní chceme nájsť podproblém, ktorý je malý, reprezentuje časť pôvodného problému a dá sa použiť na zostavenie väčšieho riešenia.
Predstavme si, že zlodej stojí pri dome $i$ a chce sa rozhodnúť, čo spraviť. Má dve možnosti:
Zlodej musí pri každom dome vedieť zistiť, ktorá z týchto možností mu prinesie väčší zisk. Na to potrebuje vedieť odpovedať na otázku "koľko najviac peňazí môžem získať z domov 1 až $i$"? Túto otázku si bude klásť pri každom dome, ale bude sa pýtať zľava doprava. Keď ide zľava doprava, dokáže odpoveď vždy odvodiť od predchádzajúcich domov.
Hodnota $D[i]$ nám bude hovoriť odpoveď na otázku "Koľko najviac peňazí môžem získať z domov 1 až $i$?". Potom pre konkrétny dom $i$:
Keď vieme obe tieto hodnoty, vyberieme si tú väčšiu z nich a tú prehlásime za odpoveď pre $D[i]$.
Jedinou výnimkou je odpoveď pre $i=1$, teda koľko zarobíme na domoch 1 až 1. Odpoveď na takúto otázku je hodnota domu č. 1 (teda $h(1)$).
Riešenie celej úlohy (koľko zarobíme na celej ulici) nájdeme na mieste $D[n]$, kde $n$ je počet domov na ulici. Teda, je to odpoveď na "koľko najviac zarobíme na domoch 1 až $n$".
Takto sme rozdelili problém na menšie podproblémy, ktoré sú menšou časťou pôvodného problému, a vieme ich vypočítať pomocou menších podproblémov.
Pri riešení úloh pomocou dynamického programovania zvyčajne postupujeme podľa nasledovného postupu: