Vad är dynamisk programmering (memoization kontra tabulering)?

Question

Accepted Answer

**Dynamisk programmering (DP)** löser problem med **överlappande delproblem** och **optimal substruktur** genom att beräkna varje delproblem en gång och återanvända resultatet. De två stilarna är **memoization** (top-down) och **tabulering** (bottom-up).

## Idén

Naiv rekursion beräknar samma delproblem exponentiellt. DP cachar dem, vilket kollapserar exponentiellt arbete till polynomialt.

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

## Tabulering (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 kontra tabulering

| | Memoization | Tabulering |
|---|------------|------------||
| Riktning | top-down rekursion | bottom-up iteration |
| Beräknar | endast nödvändiga tillstånd | alla tillstånd |
| Risk | stacköverflöde | ingen |
| Utrymme | kan trimmas | ofta reducerbar till O(1) rader |

## Komplexitet

Fibonacci: från O(2ⁿ) naiv till **O(n)** tid, O(n) (eller O(1)) utrymme.

## När man använder / fallgropar

Använd DP när delproblem **överlappar**. Definiera tillståndet och återfallet noggrant — det är den svåra delen. Om delproblem inte överlappar räcker enkel dela-och-härska.

## Varför det är viktigt

DP omvandlar svårlösliga exponentiella problem — kortaste vägar, redigeringsdistans, ryggsäck — till effektiva.

Förmågan att identifiera tillstånd och återfall är bland det mest värderade i algoritmintervjuer.

Det ligger till grund för verkliga system från diff-verktyg till bioinformatik-sekvensanpassning.