Kaj je dinamično programiranje (memoizacija v primerjavi s tabelaranjem)?

Question

Accepted Answer

**Dinamično programiranje (DP)** rešuje probleme s **prekrivajočimi se podproblemi** in **optimalno podstrukturno lastnostjo** z računanjem vsakega podproblema enkrat in ponovno uporabo rezultata. Dva slogova sta **memoizacija** (od vrha navzdol) in **tabelaranje** (od spodaj navzgor).

## Ideja

Naivna rekurzija ponovno izračuna iste podprobleme eksponentno. DP jih shranjuje, kar zruši eksponentno delo v polinomsko.

## Memoizacija (od vrha navzdol)

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

## Tabelaranje (od spodaj navzgor)

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

## Memoizacija v primerjavi s tabelaranjem

| | Memoizacija | Tabelaranje |
|---|------------|------------||
| Smer | top-down rekurzija | bottom-up iteracija |
| Izračuna | samo potrebna stanja | vsa stanja |
| Tveganje | overflow sklada | nobeno |
| Prostor | se lahko skrajša | pogosto reducibilen na O(1) vrstic |

## Kompleksnost

Fibonaccijev niz: od O(2ⁿ) naivnega na **O(n)** časa, O(n) (ali O(1)) prostor.

## Kdaj uporabiti / pasti

Uporabite DP, ko se podproblemi **prekrivajo**. Previdno definirajte stanje in ponavljajočo se relacijo — to je težak del. Če se podproblemi ne prekrivajo, je preprost divide-and-conquer dovolj.

## Zakaj je to pomembno

DP pretvori intraktabilne eksponentne probleme — najkrajše poti, razdalja med nizi, nahrbtnik — v učinkovite.

Spretnost prepoznavanja stanja in ponavljajoče se relacije je med najbolj cenjeni v algoritmičnih intervjujih.

Je temelj dejanskih sistemov od orodij za primerjavo datotek do bioinformatike poravnave zaporedij.