Mi az a dinamikus programozás (memoizálás versus tabuláció)?

Question

Accepted Answer

**A dinamikus programozás (DP)** olyan problémákat old meg, amelyeknek **átfedő részproblémái** és **optimális részstruktúrája** van, azáltal hogy minden részproblémát egyszer kiszámít és az eredményt újrahasznosítja. A két stílus a **memoizálás** (top-down) és a **tabuláció** (bottom-up).

## Az ötlet

Az agyatlan rekurzió exponenciálisan újraszámítja ugyanazokat a részproblémákat. A DP cacheli őket, exponenciális munkát polinomiális munkává alakítva.

## Memoizálás (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
```

## Tabuláció (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]
```

## Memoizálás versus tabuláció

| | Memoizálás | Tabuláció |
|---|------------|----------|
| Irány | top-down rekurzió | bottom-up iteráció |
| Kiszámít | csak szükséges állapotok | összes állapot |
| Kockázat | stack overflow | egyik sem |
| Tér | csökkenthető | gyakran O(1) sorra csökkenthető |

## Bonyolultság

Fibonacci: O(2ⁿ) naívtól **O(n)** időig, O(n) (vagy O(1)) térhez.

## Mikor kell használni / csapdák

DPt akkor használjon, ha a részproblémák **átfedésben vannak**. Az állapot és az ismétlődés gondosan definiálja — ez a nehéz rész. Ha a részproblémák nem fedik egymást, az egyszerű divide-and-conquer elég.

## Miért fontos

A DP kezelhetetlenné váló exponenciális problémákat — legrövidebb útvonalak, szerkesztési távolság, hátizsák — hatékonyakká alakítja.

Az állapot és az ismétlődés azonosításának képessége az egyik legértékesebb az algoritmus-interjúkban.

A valós rendszerek alapjait képezi a diff eszközöktől a bioinformatikai szekvencia-igazításig.

	Memoizálás	Tabuláció
Irány	top-down rekurzió	bottom-up iteráció
Kiszámít	csak szükséges állapotok	összes állapot
Kockázat	stack overflow	egyik sem
Tér	csökkenthető	gyakran O(1) sorra csökkenthető