Dynamic Programming 1: Memoization, Tabulation ve Alt Problemleri Tanımak

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Fibonacci sayılarının tanımı bir satır: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Onu doğrudan koda çevirip kaç kez çağrıldığını sayıyoruz:

public static long Calls;

// O(2^n): aynı alt problemler tekrar tekrar çözülüyor
public static long Naive(int n)
{
    Calls++;
    return n < 2 ? n : Naive(n - 1) + Naive(n - 2);
}

F(40) = 102.334.155. Bunu hesaplamak için Naive kaç kez çağrılır? Birkaç yüz mü, birkaç bin mi, birkaç milyon mu? Bir de şunu düşün: aynı hesabı 79 çağrıyla yapmak için koda ne eklemek gerekir?

Overlapping Subproblems ve Optimal Substructure

Gerçek koşunun cevabı:

fib(20) = 6,765: naive calls=21,891 (0.0 ms), memo calls=39
fib(30) = 832,040: naive calls=2,692,537 (3.3 ms), memo calls=59
fib(40) = 102,334,155: naive calls=331,160,281 (325.8 ms), memo calls=79

331 milyon çağrı. Sebebi recursion tree'sinde: F(40), F(39) ve F(38)'i çağırıyor; F(39) da F(38)'i bir kez daha çağırıyor. F(38) iki kez, F(37) üç kez, F(36) beş kez hesaplanıyor; tekrar sayıları da Fibonacci dizisini izliyor ve exponential büyüyor. Oysa farklı alt problem sayısı yalnız 41: F(0)'dan F(40)'a.

DP (Dynamic Programming), bu iki gözleme dayanan bir yöntemdir. Overlapping subproblems: aynı alt problemler defalarca karşımıza çıkıyor, o yüzden her birini bir kez çözüp sonucunu saklamak işe yarıyor. Optimal substructure: büyük problemin cevabı, alt problemlerin cevaplarından kurulabiliyor. Serinin 20. yazısında greedy için de optimal substructure gerekiyordu; fark, greedy'nin her adımda tek bir alt probleme güvenip geri kalanları hiç düşünmemesi, DP'nin ise bütün alt problemlerin cevabını bilip aralarından seçmesi. Adındaki "programming" bilgisayar programı değil, Richard Bellman'ın 1950'lerde kullandığı anlamıyla "tablo doldurarak planlama".

Fibonacci: Exponential'dan O(1) Belleğe

Birinci adım memoization (top-down): aynı recursive kodu yaz, ama bir sonucu hesaplamadan önce cache'e bak, hesapladıktan sonra cache'e yaz.

// Top-down: aynı recursion, her n bir kez hesaplanır. O(n) zaman, O(n) bellek + O(n) stack
public static long Memo(int n) => Memo(n, new long?[n + 1]);

private static long Memo(int n, long?[] memo)
{
    Calls++;
    if (n < 2) return n;
    return memo[n] ??= Memo(n - 1, memo) + Memo(n - 2, memo);
}

??= operatörü işi tek satıra indiriyor: memo[n] null ise sağ tarafı hesaplayıp yazar, değilse saklı değeri döndürür. Cache için Dictionary yerine array kullanabiliyoruz, çünkü state tek bir küçük tamsayı. Çağrı sayısı 331 milyondan 79'a iniyor: her n için en fazla iki çağrı.

İkinci adım tabulation (bottom-up): recursion'ı tamamen bırak, tabloyu küçükten büyüğe doldur. Her F(i) hesaplanırken ihtiyaç duyduğu F(i-1) ve F(i-2) zaten tabloda.

// Bottom-up: tabloyu küçükten büyüğe doldur. Recursion yok
public static long Table(int n)
{
    if (n < 2) return n;
    long[] f = new long[n + 1];
    f[1] = 1;
    for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    return f[n];
}

Üçüncü adım, tabloda gerçekten neye ihtiyaç olduğuna bakmak: her adım yalnız son iki değeri kullanıyor. Tablonun geri kalanı çöp.

// Yalnız son iki değer gerekli: O(1) bellek
public static long Iterative(int n)
{
    long prev = 0, current = 1;
    if (n == 0) return 0;
    for (int i = 2; i <= n; i++) (prev, current) = (current, prev + current);
    return current;
}

Dört versiyonu BenchmarkDotNet ile n = 30 için ölçtüm. Ölçümler Apple M5 (10 çekirdek), macOS 27.0.1, .NET 10.0.13, BenchmarkDotNet 0.15.8 ile alındı. Benchmark'ları tek tek çalıştırdım ama makinede paralel işler vardı; mutlak sayılara değil oranlara bak.

| Method    | N  | Mean             | Ratio | Allocated |
|---------- |--- |-----------------:|------:|----------:|
| Naive     | 30 | 2,100,447.155 ns | 1.001 |         - |
| Memo      | 30 |       100.982 ns | 0.000 |     520 B |
| Table     | 30 |        26.285 ns | 0.000 |     272 B |
| Iterative | 30 |         7.370 ns | 0.000 |         - |

Naive 2,1 ms, memoization 101 ns: yaklaşık 20.000 kat. Memo ile tablo arasındaki 4 katlık fark recursion'ın ve long? array'inin bedeli (nullable her slot için ek bir bool ve hizalama, 31 slot için 520 byte). Iterative versiyon allocation yapmıyor ve 7 ns'de bitiyor. Ratio sütununda 0.000 görmen, oranın üç basamağa sığmayacak kadar küçük olmasından. Bu dört adım, hemen her DP probleminde izlenebilecek bir yol: önce doğru recursive tanım, sonra memoization, sonra tablo, sonra tablonun gerçekten gereken kısmı.

Beş Adımlı Tarif

Yeni bir problemde DP'ye bakarken şu beş soruyu sırayla cevapla:

• State: bir alt problemi tek başına tanımlayan en küçük bilgi ne? Fibonacci'de n; para üstünde kalan tutar.
• Transition: bir state'in cevabı daha küçük state'lerin cevaplarından nasıl kurulur? F(n) = F(n-1) + F(n-2).
• Base case: recursion'ı bitiren, cevabı doğrudan bilinen state'ler hangileri? F(0) = 0, F(1) = 1.
• Hesaplama sırası: tabloyu hangi sırayla doldurursan her state'in ihtiyaç duyduğu cevaplar hazır olur? Küçük n'den büyüğe.
• Cevap: tablonun hangi hücresi asıl sorunun cevabı? f[n].

State'i doğru seçmek işin en zor kısmı ve hataların çoğu orada. Aşağıdaki örneklerde her birini bu beş adımla okuyacağız.

Climbing Stairs ve House Robber

Climbing stairs: n basamaklı bir merdivene her adımda 1 ya da 2 basamak çıkarak kaç farklı şekilde çıkılır? State: kaçıncı basamaktayız. Transition: i'nci basamağa ya i-1'den ya da i-2'den gelinir, yani ways(i) = ways(i-1) + ways(i-2). Base case: ways(0) = ways(1) = 1. Kılık değiştirmiş Fibonacci; aynı O(1) bellek tekniği:

// ways[i] = ways[i-1] + ways[i-2]
public static long ClimbStairs(int n)
{
    long a = 1, b = 1; // ways(0), ways(1)
    for (int i = 2; i <= n; i++) (a, b) = (b, a + b);
    return b;
}

House robber, Bookstore kılığında: bir kampanya takviminde ardışık günlere indirim koyamıyoruz (iki gün üst üste indirim, müşteriyi indirim beklemeye alıştırıyor) ve her günün beklenen ek cirosu farklı. Ardışık olmayan günleri seçerek toplam ciroyu en büyük yap. State: ilk i gün. Transition: i'nci günü ya seçmeyiz (cevap ilk i-1 günün cevabı) ya da seçeriz (cevap ilk i-2 günün cevabı artı bugünün cirosu); best(i) = max(best(i-1), best(i-2) + value(i)).

// best[i] = max(best[i-1], best[i-2] + value[i])
public static int HouseRobber(int[] values)
{
    int skip = 0, take = 0; // önceki elemana kadar en iyi: onsuz / onunla
    foreach (int v in values)
    {
        (skip, take) = (Math.Max(skip, take), skip + v);
    }

    return Math.Max(skip, take);
}

house robber [2,7,9,3,1]: 12

Cevap 12: 1., 3. ve 5. günler (2 + 9 + 1). En büyük tek değer 9'u seçip komşularını atan greedy de burada 12 bulur, ama [2, 7, 9, 8] gibi bir dizide greedy 9 + 2 = 11 bulurken DP 7 + 8 = 15 bulur (bu durum testlerde de var). Greedy tarafını küçük denemeye bırakıyorum.

Coin Change: Minimum Para ve Kaç Yol

Bir önceki yazıda greedy'nin yanıldığı problemi DP ile çözelim. Minimum para: state kalan tutar, transition "son verdiğin para c ise, a - c tutarını en iyi şekilde vermiş olmalısın", yani best(a) = min(best(a - c) + 1).

// best[a] = her c parası için best[a - c] + 1'in minimumu; tutar verilemiyorsa -1
public static int MinCoins(int[] coins, int amount)
{
    int[] best = new int[amount + 1];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
    {
        foreach (int c in coins)
        {
            if (c <= a && best[a - c] != int.MaxValue)
            {
                best[a] = Math.Min(best[a], best[a - c] + 1);
            }
        }
    }

    return best[amount] == int.MaxValue ? -1 : best[amount];
}

min coins {1,3,4} -> 6: 2

Maliyet O(tutar × para sayısı). Greedy'nin 3 para verdiği yerde 2 (3 + 3). int.MaxValue'yu "verilemez" anlamında kullanırken best[a - c] + 1'in taşmaması için önce kontrol ediyoruz.

Kaç yol: 1, 2 ve 5'lik paralarla 5 birim kaç farklı şekilde verilir? Burada DP'nin en sinsi tuzaklarından biri var: iki döngünün sırası. Paralar dış döngüdeyse her para sırayla "kullanıma açılır" ve 1 + 2 + 2 ile 2 + 1 + 2 aynı kombinasyon olarak bir kez sayılır. Tutar dış döngüdeyse her tutara her paradan gelinebilir ve sıralar ayrı sayılır:

// Kombinasyon sayısı (sıra önemsiz): paralar DIŞ döngüde
public static long CountWays(int[] coins, int amount)
{
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    foreach (int c in coins)
        for (int a = c; a <= amount; a++)
            ways[a] += ways[a - c];
    return ways[amount];
}

// Döngüler yer değiştirince sıralı diziler sayılır (1+2 ve 2+1 iki kez): başka bir soru
public static long CountSequences(int[] coins, int amount)
{
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    for (int a = 1; a <= amount; a++)
        foreach (int c in coins)
            if (c <= a) ways[a] += ways[a - c];
    return ways[amount];
}

ways {1,2,5} -> 5: combinations=4, sequences=9

4 kombinasyon: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1. 9 sıralı dizi ise farklı bir sorunun, "kasaya paraları hangi sırayla koyabilirim" sorusunun cevabı. İkisi de geçerli DP; hangisinin istendiğini problem tanımı söyler ve kod tek bir satırın yeriyle değişir. Testler ikisini birden sabitliyor:

[Fact]
public void CountWays_CountsCombinationsNotSequences()
{
    Assert.Equal(4, DynamicProgramming.CountWays([1, 2, 5], 5));
    Assert.Equal(9, DynamicProgramming.CountSequences([1, 2, 5], 5));
}

Test run summary: Passed!
  total: 17
  failed: 0
  succeeded: 17
  skipped: 0
  duration: 347ms

Top-Down mu, Bottom-Up mı

Memoization'ın avantajı yazımının kolaylığı: recursive tanımı olduğu gibi kodlar, bir cache eklersin. Yalnız gerçekten ihtiyaç duyulan state'leri hesaplar; state uzayı büyük ama cevap için küçük bir kısmı yetiyorsa bu önemli bir kazanç. Dezavantajı recursion: her çağrı bir stack frame'i, ve derinlik state zincirinin uzunluğu kadar. Fibonacci'yi n = 1.000.000 ile memoization'la çağırdım:

public static void Overflow() => Console.WriteLine(Fibonacci.Memo(1_000_000));

Stack overflow.
Repeated 104510 times:
--------------------------------
   at Algorithms.Paradigms.Fibonacci.Memo(Int32, System.Nullable`1<Int64>[])
--------------------------------
   at Algorithms.Paradigms.Fibonacci.Memo(Int32)
   at Demo21.Overflow()
   at Program.<Main>$(System.String[])

Process 134 çıkış koduyla öldü; serinin 5. yazısında gördüğümüz gibi StackOverflowException catch edilemez. Bu makinedeki varsayılan stack'te yaklaşık 104.500 frame sığdı (sayı stack boyutuna ve frame büyüklüğüne bağlı). Uyarı Fibonacci'ye özgü değil: top-down yazılmış herhangi bir DP, state zinciri uzunsa (örneğin uzun bir string üzerinde karakter karakter ilerleyen bir memoization) aynı duvara çarpar.

Tabulation'ın avantajları tam tersi: recursion yok, stack derinliği sorunu yok, döngüler cache dostu ve tablonun yalnız gereken kısmını tutma (O(1) Fibonacci, iki satırlık knapsack) gibi bellek optimizasyonlarına açık. Dezavantajı, hesaplama sırasını senin bulman gerekmesi ve bazen hiç kullanılmayacak state'leri de hesaplaması. Pratik kural: önce top-down yaz, doğruluğunu testlerle sabitle, sonra performans ya da derinlik gerekiyorsa bottom-up'a çevir ve iki versiyonu birbirine karşı test et.

Üretimde Dikkat

Taşma ve sayı tipi. F(92) long'a sığan son Fibonacci sayısı, F(93) sığmaz; "kaç yol" türünden sayımlar da çok hızlı büyür. Testteki F(90) bu yüzden seçildi. Büyük sayımlar için checked bağlamı (taşınca exception), UInt128 ya da BigInteger kullan; ya da problem "modulo 10⁹+7" gibi bir şey istiyorsa her toplamada mod al.

Memo'nun ömrü. Memoization sonuçlarını static bir dictionary'de tutmak (uygulama boyunca yaşayan bir cache) başlangıçta cazip görünür ama bellek sızıntısına dönüşebilir ve thread-safe değildir. Bizim Memo'muz cache'i her çağrıda yeni oluşturuyor. Uygulama genelinde paylaşılan bir cache gerekiyorsa sınırı ve süresi olan gerçek bir cache kullan; ASP.NET Core'daki cache seçeneklerini ilgili serilerde ele aldık.

State boyutunu hesapla. Tablo boyutu state sayısı kadar. Tutar 10⁹ olan bir para üstü problemi O(tutar) bellek ister ve 4 GB'lık bir int[] demektir; bu durumda DP doğru araç olmayabilir ya da state'i yeniden tanımlamak gerekir.

Static sayaçlar ve paralel testler. Bu yazıdaki Fibonacci.Calls gösterim için static bir sayaç; xUnit test class'larını paralel çalıştırdığı için iki test aynı sayacı artırırsa assert'ler rastgele kırılır. Ölçüm için sayaç kullanıyorsan onu instance'a ya da parametreye taşı.

Sık Düşülen Tuzaklar

Memo key'ini yanlış tasarlamak. Kaç yol problemini top-down yazalım: state (kalan tutar, hangi paradan itibaren kullanabileceğim). Cache key'ini yalnız tutar yapan bir versiyonla karşılaştırdım:

long Ways(int amount, int index, Dictionary<(int, int), long> memo)
{
    if (amount == 0) return 1;
    if (amount < 0 || index == coins.Length) return 0;
    if (memo.TryGetValue((amount, index), out long cached)) return cached;
    long result = Ways(amount - coins[index], index, memo)   // coins[index]'i tekrar kullan
                + Ways(amount, index + 1, memo);             // coins[index]'i bir daha kullanma
    return memo[(amount, index)] = result;
}

long WaysWrongKey(int amount, int index, Dictionary<int, long> memo)
{
    if (amount == 0) return 1;
    if (amount < 0 || index == coins.Length) return 0;
    if (memo.TryGetValue(amount, out long cached)) return cached; // HATA: index'i yok sayıyor
    long result = WaysWrongKey(amount - coins[index], index, memo)
                + WaysWrongKey(amount, index + 1, memo);
    return memo[amount] = result;
}

top-down ways, key=(amount,index): 4
top-down ways, key=amount only:    9

Yanlış key'li versiyon "3 birim, 2'lik paradan itibaren" sorusunun cevabını "3 birim, 1'lik paradan itibaren" sorusunun cevabıyla karıştırıyor ve 9 diyor. Exception yok, sonuç makul görünüyor. Kural: cache key'i, fonksiyonun sonucunu etkileyen parametrelerin tamamı olmalı. Memo'lu bir fonksiyonun sonucu, key'e girmeyen bir parametreye bağlıysa cache yanlış cevap verir.

Top-down çözümde recursion derinliği. Yukarıda gördük; büyük input'ta process ölür ve catch edilemez. Derinliği state zincirinin uzunluğu belirler, input boyutu değil; uzun bir zincir ihtimali varsa bottom-up'a geç.

Base case'leri unutmak ya da yanlış koymak. ways[0] = 1 ("0 birimi vermenin bir yolu var: hiçbir şey vermemek") sezgiye aykırı gelebilir, ama 0 yaparsan bütün tablo sıfır çıkar. Base case'i en küçük birkaç input için elle hesaplayıp testle sabitle.

Döngü sırasını önemsiz sanmak. CountWays ve CountSequences arasındaki tek fark iki satırın yeri ve cevaplar 4 ile 9. Tablo doldurmada sıra, state tanımının bir parçasıdır.

Küçük Bir Deneme

★☆☆ HouseRobber'ı [2, 7, 9, 8] ile çalıştır, sonra "en büyük değeri seç, komşularını at, tekrarla" greedy'sini yaz ve sonuçları karşılaştır. Rastgele 1.000 dizide greedy'nin kaç kez yanıldığını say.

★★☆ MinCoins'i hangi paraların kullanıldığını da döndürecek şekilde genişlet: her tutar için son kullanılan parayı ayrı bir array'de tut ve 6 için [3, 3]'ü geri kur.

★★★ Memoization'lı Fibonacci'yi derinlik sorunu olmadan büyük n için çalıştır: önce memo'yu küçük n'den büyüğe "ısıtarak" (F(1000), F(2000), ... sırayla çağırarak) recursion derinliğini sınırla, sonra aynı sonucu BigInteger ve tabulation ile doğrula. F(10.000) kaç basamaklı?

Bu yazıda tek boyutlu state'lerle çalıştık: bir sayı, bir tutar, bir gün. Bir sonraki ve serinin son yazısında state iki boyuta çıkıyor: iki string'in prefix'leri, bir bütçe ve bir eleman sayısı. Edit distance ile "Bunu mu demek istediniz?", LCS (Longest Common Subsequence) ile diff ve 0/1 knapsack ile kampanya bütçesi; ardından seri boyunca gördüğümüz pattern'leri bir karar tablosunda toparlayacağız.