Co je dynamické programování (memoization vs tabulation)?

Question

Accepted Answer

**Dynamické programování (DP)** řeší problémy s **overlapping subproblems** a **optimal substructure** výpočtem každého podproblému jednou a znovupoužitím výsledku. Dva styly jsou **memoization** (top-down) a **tabulation** (bottom-up).

## Myšlenka

Naivní rekurze počítá stejné podproblémy exponenciálně znovu. DP je cachuje, čímž sbaluje exponenciální práci na polynomiální.

## Memoization (top-down)

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # cache results automatically
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # each n computed once
```

## Tabulation (bottom-up)

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build up from base cases
    return dp[n]
```

## Memoization vs tabulation

| | Memoization | Tabulation |
|---|------------|------------|
| Směr | top-down rekurze | bottom-up iterace |
| Počítá | pouze potřebné stavy | všechny stavy |
| Riziko | stack overflow | žádné |
| Prostor | lze zmenšit | často reducibilní na O(1) řádky |

## Složitost

Fibonacci: z O(2ⁿ) naivního na **O(n)** čas, O(n) (nebo O(1)) prostor.

## Kdy použít / Pitfalls

Využijte DP, když se podproblémy **překrývají**. Pečlivě definujte stav a rekurenci — to je ta těžká část. Pokud se podproblémy nepřekrývají, prostý divide-and-conquer stačí.

## Proč je to důležité

DP převádí nezvladatelné exponenciální problémy — nejkratší cesty, edit distance, knapsack — na efektivní.

Dovednost identifikování stavu a rekurence patří mezi nejcennější v algoritmických pohovorech.

Zakládá reálné systémy od diff nástrojů až po bioinformatické zarovnání sekvencí.

	Memoization	Tabulation
Směr	top-down rekurze	bottom-up iterace
Počítá	pouze potřebné stavy	všechny stavy
Riziko	stack overflow	žádné
Prostor	lze zmenšit	často reducibilní na O(1) řádky