Překrývající se podproblémy: Když řešíš velký úkol, pořád narážíš na stejné malé úkoly. (Např. při výpočtu Fibonacciho posloupnosti počítáš F(3) pořád dokola).
Memoizace (Shora dolů / Top-Down)
- Jak to funguje: Začneš od velkého problému. Jakmile narazíš na něco, co neznáš, vypočítáš to a zapíšeš si výsledek do “deníčku” (
memo). - Příklad z tvého kódu: Funkce se ptá: “Mám už v
memovýsledek pro n?” Pokud ano, hned ho vrátí. Pokud ne, vypočítá ho a uloží.
Tabulace (Zdola nahoru / Bottom-Up)
- Jak to funguje: Nejdřív vyřešíš ty nejjednodušší věci a výsledky skládáš do tabulky (pole), dokud se nedopracuješ k cíli.
- Příklad z tvého kódu: Vytvoříš si pole
dp. Nejdřív vyplníšdp[1]adp[2]. Pak v cykluforpočítáš další políčka na základě těch předchozích.
Když chceš po počítači Fibonacci(5) bez DP, dělá tohle:
- Chce
Fib(5), tak musí spočítatFib(4)aFib(3). - Aby spočítal
Fib(4), musí spočítatFib(3)aFib(2). - STOP! Vidíš to? Počítač už teď počítá
Fib(3)dvakrát! - A u
Fib(100)by ty samé malé kousky počítal miliardkrát.