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

Rekureze:
- faktorial
- fibonachiho cisla (rekurzi, rekurze s memoizaci, DP)


--------------------------------------------------
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

https://medium.com/launch-school/recursive-fibonnaci-method-explained-d82215c5498e

2. Příklad teoreticky 
- metodu DP ukážeme a demonstrujeme na příkladu optimalizace uzávorkování násobení matic
- viz příloha
- otazky: 
-- jaka je slozitost algoritmu?
-- co nam algoritmus vrati? (analogie s dijkstrou; je to, to co jsme chteli? a jak situaci vyresit?)

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)

Rekurzivní definování problému top-down
Rekurzivní definování problému top-down s memoizací
Rekurzivní definování problému bottom-up
Odstranění rekurze - DP 



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


Příklad Lezení do schodů

# Climbing stairs
# There is a staircase of n steps and you can climb either 1 or 2 steps at a time.
# We need to count and return total number of unique ways to reach the n'th stair.
# The order of steps matters.


# 1. Solve problem by pure recursion (brutal force recursion)
# 1.2 Find recursive problem description
# 1.4 Implement algorithm

# 2. Solve problem by dynamic programing aproach
# 2.2 Find dynamic programing problem description
# 2.4 Implement algorithm


# note: https://www.enjoyalgorithms.com/blog/climbing-stairs-problem