Dinamik programlama (memoization vs tabulasyon) nedir?

Question

IT Interview Practice · Accepted Answer

**Dinamik programlama (DP)** **çakışan alt problemler** ve **optimal alt yapı** bulunan problemleri, her alt problemi bir kez hesaplayıp sonucu yeniden kullanarak çözer. İki stil **memoization** (top-down) ve **tabulasyon** (bottom-up)'dur.

## Fikir

Naif özyineleme aynı alt problemleri üssel olarak yeniden hesaplar. DP onları önbelleğe alır, üssel işi polinomik işe çökerek.

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

## Tabulasyon (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 vs tabulasyon

| | Memoization | Tabulasyon |
|---|------------|------------||
| Yön | top-down özyineleme | bottom-up yineleme |
| Hesaplar | yalnızca gereken durumlar | tüm durumlar |
| Risk | stack taşması | hiçbiri |
| Alan | kırpılabilir | genellikle O(1) satırına indirgenebilir |

## Karmaşıklık

Fibonacci: O(2ⁿ) naiften **O(n)** zamana, O(n) (veya O(1)) alana.

## Ne zaman kullanılacağı / tuzaklar

Alt problemler **çakıştığında** DP kullanın. Durumu ve yinelenmeyi dikkatle tanımlayın — bu zor kısım. Alt problemler çakışmıyorsa, basit böl ve fethet yeterlidir.

## Neden önemli

DP çözülmez üssel problemleri — en kısa yollar, düzenleme mesafesi, sırt çantası — verimli olanlara dönüştürür.

Durum ve yinelenmeyi tanımlama becerisi algoritma mülakatlarında en çok değerlenen yetenekler arasındadır.

Diff araçlarından biyoinformatik dizi hizalamasına kadar gerçek sistemlerin temelini oluşturur.

Fikir

Memoization (top-down)

Tabulasyon (bottom-up)

Memoization vs tabulasyon

Karmaşıklık

Ne zaman kullanılacağı / tuzaklar

Neden önemli

İlgili sorular