Dynamické programování

1. DP - úvod
2. Příklad teoreticky - optimalizace uzávorkování násobení matic 
3. Příklad prakticky - optimalizace uzávorkování násobení matic


--------------------------------------------------
Poznámky
--------------------------------------------------
1. DP - co víme? opakování

Co je to DP?
Přečíst:
- https://en.wikipedia.org/wiki/Dynamic_programming
--první část před overview

- Moc nevíme, co to DP je, když už něco víme/si myslíme (třeba rekurze s pamatováním) tak je vymezení hodně extenzivní a nacpe se tam "vše" (třeba součet všech hodnot v bin. stromě)
- (zajímavý) https://www.enjoyalgorithms.com/blog/introduction-to-dynamic-programming


Pozorování: 
DP se (na školách) učí na příkladech - proč?
Víme, na které problémy můžeme metodu DP použít? Vždyť DP "nemá žádný vzorec pro dosazení". 
- https://en.wikipedia.org/wiki/Bellman_equation
- https://en.wikipedia.org/wiki/Optimal_substructure

2. Příklad teoreticky 
- metodu DP ukážeme a demonstrujeme na příkladu optimalizace uzávorkování násobení matic
- viz příloha

3. Příklad prakticky - a ted implementovat
příklad implementace  např.: https://www.geeksforgeeks.org/csharp-program-for-matrix-chain-multiplication-dp-8/
- je tam rekurzivní výpočet i 3for cykly
- kdyby se začalo implementací, tak rekontruovat logiku algoritmu bývá nejasné obtížné
- kód doslova pár řádek, ale překlopení z teoretického pochopení do kódu nakonec nebývá tak simple (ze zkušenosti)



Idea (neformálně): 
1. Rekurzivní popis problému
2. Rekurze + Memoizace (rekurze s "fikaným" zapamatováním a využíváním mezivýsledků; nepočítat znovu, co už znám) (memoizace top-down)
3. "Odstranění rekurze" (uvědomím si, že rekurzi nepotřebuji) a skládám řešení z již vypočtených řešení (opakujících se) subproblémů (tabularizace - bottom-up)

fajn znázornění rozdílů demonstrované na fib cislech: 
https://www.enjoyalgorithms.com/blog/introduction-to-dynamic-programming