Dynamické programování
Dle Holanovy přednášky z
Programování 23. dubna.
Rada do života;): Když «přirozený» algoritmus má exponenciální složitost, měli bychom se zamyslet nad řešením pomocí dynamického programování.
Vhodné na optimalizační úlohy, kdy se optimální řešení skládá z optimálních řešení «menších» úloh.
Motivační úlohy
Více méně podle stoupající složitosti (tzn. v pořadí, v němž byly řešeny na přednášce):
- Úloha Záhony
- Úloha Děti Do Skupin
- Úloha Nejdelší Rostoucí Podposloupnost
- Úloha Editační Vzdálenost
- (násobení několika matic, tohle si nepíšu, už jsme to dělali na cvičeních, doplňte to někdo...)
- Úloha Optimální Vyhledávací Strom
Často, když mám řešení rekurzí a přidám do něj cachování výsledků, získám ekvivalent dynamického řešení (jenom tak trochu z druhého konce, taky ale nemusím řešit pořadí vyplňování tabulky, protože se mi vyřeší samo).
