Çfarë është programimi dinamik (memoizimi kundrejt tabelimit)?

Question

Accepted Answer

**Programimi dinamik (DP)** zgjidh problemat me **nënproblema që mbivendosen** dhe **strukturë optimale të nënproblemave** duke llogaritur çdo nënproblem një herë dhe duke rikërdorur rezultatin. Dy stilet janë **memoizimi** (top-down) dhe **tabelimi** (bottom-up).

## Ideja

Rekurzioni naiv rillogarit të njëjtat nënproblema në mënyrë eksponenciale. DP i memorizon ato, duke shndërruar punën eksponenciale në polinomiale.

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

## Tabelimi (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]
```

## Memoizimi kundrejt tabelimit

| | Memoizimi | Tabelimi |
|---|------------|------------||
| Drejtim | top-down rekurzione | bottom-up iterimi |
| Llogarit | vetëm shtetet e nevojshme | të gjitha shtetet |
| Rrezik | tejmbushje e stack | asnjë |
| Hapësira | mund të përmirësohet | shpesh e reduktueshme në O(1) rreshta |

## Kompleksiteti

Fibonacci: nga O(2ⁿ) naiv në **O(n)** kohë, O(n) (ose O(1)) hapësirë.

## Kur të përdoret / grackësi

Përdorni DP kur nënproblemat **mbivendosen**. Përcaktoni gjendjen dhe rekurencën me kujdes — ky është pjesa e vështirë. Nëse nënproblemat nuk mbivendosen, një ndarje e thjeshtë-dhe-pushte është e mjaftueshme.

## Pse ka rëndësi

DP e shndërron intraktable problemat eksponencialë — rrugat më të shkurtra, distanca redaktuese, çanta — në efikase.

Artizania e identifikimit të gjendjes dhe rekurencës është ndër më të vlerësuarit në intervista të algoritmeve.

Është themelore për sistemet reale nga mjete diff në lidhjen e sekuencës bioinformatike.