Aralık 24, 2024
Okuma süresi: 2 dakika
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 programlama kullanılabilecek bir problemi tanımlamak için şu iki özellik önemlidir:
Alt Problem Optimalitesi: Büyük bir problemin çözümü, daha küçük alt problemlerinin optimal çözümlerine dayanır.
Alt Problemlerin Çakışması: Alt problemler birden fazla kez çözülür.
Memoization (Bellekleme):
Alt problemlerin sonuçlarını bir tabloya kaydederek tekrar hesaplamayı önler.
Rekürsif bir yaklaşım ile çalışır.
Tabulation (Tablolama):
Çözümleri küçük alt problemlerden başlayarak aşamalı olarak hesaplar.
İteratif bir yaklaşım kullanır.
Fibonacci Sayıları Hesaplama:
Rekürsif yöntemle hesaplandığında tekrar eden hesaplamaları önlemek için dinamik programlama kullanılabilir.
Knapsack Problemi:
Belirli bir kapasiteye sahip bir çantaya maksimum değeri elde edecek şekilde öğeleri yerleştirme problemidir.
En Uzun Ortak Alt Dizi (Longest Common Subsequence - LCS):
İki dizi arasındaki en uzun ortak alt diziyi bulma problemidir.
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.
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
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, 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.
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.