Dinamik Programlama: Temel Kavramlar ve Örnekler

Dinamik Programlama: Temel Kavramlar ve Örnekler

Dinamik programlama, büyük problemleri daha küçük alt problemlere ayırarak çözmeyi amaçlayan etkili bir algoritma tasarım tekniğidir. Genellikle rekürsif problemlerle çalışırken, aynı alt problemin birden fazla kez çözülmesini önlemek için önceki sonuçları kaydederek (memoization) veya tablolama (tabulation) kullanarak performansı artırır.

Dinamik Programlamanın Özellikleri

Dinamik programlama kullanılabilecek bir problemi tanımlamak için şu iki özellik önemlidir:

1. Alt Problem Optimalitesi: Büyük bir problemin çözümü, daha küçük alt problemlerinin optimal çözümlerine dayanır.

2. Alt Problemlerin Çakışması: Alt problemler birden fazla kez çözülür.

Dinamik Programlama Teknikleri

1. Memoization (Bellekleme):

   • Alt problemlerin sonuçlarını bir tabloya kaydederek tekrar hesaplamayı önler.

   • Rekürsif bir yaklaşım ile çalışır.

2. Tabulation (Tablolama):

   • Çözümleri küçük alt problemlerden başlayarak aşamalı olarak hesaplar.

   • İteratif bir yaklaşım kullanır.

Popüler Dinamik Programlama Problemleri

1. Fibonacci Sayıları Hesaplama:

   • Rekürsif yöntemle hesaplandığında tekrar eden hesaplamaları önlemek için dinamik programlama kullanılabilir.

2. Knapsack Problemi:

   • Belirli bir kapasiteye sahip bir çantaya maksimum değeri elde edecek şekilde öğeleri yerleştirme problemidir.

3. En Uzun Ortak Alt Dizi (Longest Common Subsequence - LCS):

   • İki dizi arasındaki en uzun ortak alt diziyi bulma problemidir.

4. Edit Mesafesi (Edit Distance):

   • Bir diziyi başka bir diziye dönüştürmek için gereken minimum düzenleme adımını bulma problemidir.

Örnek Kod: Fibonacci Hesaplama (Memoization ile)

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1

    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

# Örnek kullanım
print(fibonacci(10))  # Çıktı: 55

Örnek Kod: Knapsack Problemi (Tabulation ile)

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# Örnek kullanım
weights = [1, 2, 3]
values = [10, 20, 30]
capacity = 5
print(knapsack(weights, values, capacity))  # Çıktı: 50

Dinamik Programlama ve Zaman Karmaşıklığı

Dinamik programlama, hesaplamaları azaltarak zaman karmaşıklığını önemli ölçüde düşürebilir. Örneğin, basit bir Fibonacci algoritmasının O(2^n) olan karmaşıklığı, dinamik programlama ile O(n)'ye düşer.

Sonuç

Dinamik programlama, karmaşık problemleri çözmek için güçlü bir araçtır. Fibonacci, Knapsack ve LCS gibi klasik problemlerde etkili çözümler sunar. Bu tekniği anlamak ve uygulamak, algoritma tasarımında önemli bir yetkinlik kazandırır.