Kas yra dinaminis programavimas (memoization vs tabulation)?

Question

IT Interview Practice · Accepted Answer

**Dinaminis programavimas (DP)** sprendžia problemas su **persidengusiais pobroblėmais** ir **optimaliu postruktūru**, apskaičiavus kiekvieną pobroblėmą vieną kartą ir iš naujo naudojant rezultatą. Du stiliai yra **memoization** (nuo viršaus į apačią) ir **tabulation** (nuo apačios į viršų).

## Idėja

Naivi rekursija iš naujo apskaičiuoja tuos pačius pobroblėmus eksponentiškai. DP juos talpina, sumažindama eksponentinį darbą į polinomą.

## Memoization (nuo viršaus į apačią)

```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 (nuo apačios į viršų)

```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 |
|---|------------|------------|
| Kryptis | nuo viršaus į apačią rekursija | nuo apačios į viršų iteracija |
| Apskaičiuoja | tik reikalingos būsenos | visos būsenos |
| Rizika | stack overflow | nėra |
| Vieta | gali būti mažinta | dažnai sumažiinama iki O(1) eilučių |

## Sudėtingumas

Fibonačis: iš O(2ⁿ) naiviausios į **O(n)** laiką, O(n) (arba O(1)) vietą.

## Kada naudoti / spąstai

Naudokite DP, kai pobroblėmės **persidena**. Kruopščiai apibrėžkite būseną ir pasikartojimą — tai sudėtinga dalis. Jei pobroblėmės nesidena, paprastas dalyti-ir-valdyti yra pakankamas.

## Kodėl tai svarbu

DP paverčia neišsprendžiamas eksponentines problemas — trumpiausius kelius, redagavimo nuotolį, kuprinę — efektyviai sprendžiamomis.

Būsenos ir pasikartojimo nustatymo įgūdis yra vienas iš labiausiai vertintų algoritmo pokalbių.

Jis yra realiųjų sistemų, pradedant skirtumų įrankiais, baigiant bioinformatikos sekų lygiavimais, pagrindas.

	Memoization	Tabulation
Kryptis	nuo viršaus į apačią rekursija	nuo apačios į viršų iteracija
Apskaičiuoja	tik reikalingos būsenos	visos būsenos
Rizika	stack overflow	nėra
Vieta	gali būti mažinta	dažnai sumažiinama iki O(1) eilučių

Idėja

Memoization (nuo viršaus į apačią)

Tabulation (nuo apačios į viršų)

Memoization vs tabulation

Sudėtingumas

Kada naudoti / spąstai

Kodėl tai svarbu

Susiję klausimai