- Temel durumu ve özyinelemeli adımı olan bir fonksiyon yazmak ve çağrı yığıtını izlemek
- Bir problemin DP ile çözülebileceğini tanımak ve yineleme bağıntısını kurmak
- Sırt çantası ve LCS tablolarını doldurmak ve en iyi çözümü geri kurmak
- Açgözlü bir algoritmanın ne zaman başarısız olduğunu göstermek
Fibonacci sayılarını doğrudan F(n) = F(n − 1) + F(n − 2) formülüyle programlarsan, bilgisayar F(40) için yüz milyondan fazla fonksiyon çağrısı yapar. Yalnızca birkaç satır ekleyince aynı program F(90)'ı bile anında bulur. Bu derste bu “sihrin”, yani dinamik programlamanın nasıl çalıştığını, önce de temeli olan özyinelemeyi öğreneceğiz.
Özyineleme ve çağrı yığıtı
Bir fonksiyonun problemi kendisinin daha küçük bir kopyası aracılığıyla çözmesi. Her özyinelemeli fonksiyonun iki parçası vardır: temel durum (cevap doğrudan bilinir, özyineleme durur) ve özyinelemeli adım (problem temel duruma doğru küçültülür).
- n · (n − 1)!özyinelemeli adım
- 0! = 1temel durum
fact(n) fonksiyonu n == 0 iken 1, aksi hâlde n * fact(n - 1) döndürür. fact(4) çağrılınca yığıtta ne olur?
Çözümü gösterÇözümü gizle
fact(4) → fact(3) → fact(2) → fact(1) → fact(0) = 1 — temel durum, yığıtta 5 çerçeve var.
Çıkış (çerçeveler ters sırayla kapanır):
fact(1) = 1 · 1 = 1
fact(2) = 2 · 1 = 2
fact(3) = 3 · 2 = 6
fact(4) = 4 · 6 = 24.
Süre O(n), yığıt belleği de O(n): her çağrı cevabı gelene kadar yığıtta bekler.
Örtüşen alt problemler ve bellekleme
Basit özyinelemeli Fibonacci'de fib(5), fib(3)'ü iki kez, fib(2)'yi üç kez çağırır: aynı alt problemler tekrar tekrar çözülür. Çağrı sayısı, cevabın kendisi gibi üstel büyür: calls(n) = 2F(n + 1) − 1. Bellekleme (yukarıdan aşağıya) her alt problemin cevabını bir sözlükte saklar ve ikinci kez hesaplamaz; tablolama (aşağıdan yukarıya) ise cevapları küçükten büyüğe bir döngüyle doldurur.
- T(n)basit özyinelemeli fib(n)'in çalışma süresi
- φaltın oran
Bellekleme ile her fib(k) bir kez hesaplanır: n + 1 alt problem × O(1) iş = O(n). Üstelden doğrusala!
from functools import lru_cache
calls = 0
def fib_naive(n):
global calls
calls += 1
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
def fib_table(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_naive(25), 'naive calls:', calls)
print(fib_memo(25), 'memo calls:', fib_memo.cache_info().misses)
print(fib_table(90))▸ Beklenen çıktı
75025 naive calls: 242785 75025 memo calls: 26 2880067194370816120
lru_cache ile ise yalnızca 26 farklı alt problem hesaplanır. Tablo sürümü F(90)'ı O(1) bellekle anında bulur.Klasik DP: sırt çantası ve LCS
0/1 sırt çantası: ağırlıkları wᵢ, değerleri vᵢ olan eşyalardan W kapasiteli bir çantaya toplam değer en büyük olacak biçimde seçim yap (her eşya ya alınır ya alınmaz). i. eşya için iki seçenek vardır, almamak ya da almak; iyi olanı tutarız.
- dp[i][c]ilk i eşyayla c kapasitede elde edilen en büyük değer
- wᵢ, vᵢi. eşyanın ağırlığı ve değeri (ikinci seçenek yalnızca wᵢ ≤ c iken)
Süre ve bellek O(n · W). Bu sözde polinom bir karmaşıklıktır: W'nin bit sayısına göre üsteldir.
W = 5. Eşyalar (ağırlık, değer): 1: (1, 1), 2: (2, 3), 3: (3, 4), 4: (4, 5). En büyük değeri ve seçilen eşyaları bul.
Çözümü gösterÇözümü gizle
i = 1: [0, 1, 1, 1, 1, 1]
i = 2: [0, 1, 3, 4, 4, 4] (örneğin c = 3: max(1, dp[1][1] + 3 = 4) = 4)
i = 3: [0, 1, 3, 4, 5, 7] (c = 5: max(4, dp[2][2] + 4 = 7) = 7)
i = 4: [0, 1, 3, 4, 5, 7] (c = 5: max(7, dp[3][1] + 5 = 6) = 7)
Cevap dp[4][5] = 7.
Geri kurma: dp[4][5] = dp[3][5] → 4 alınmamış; dp[3][5] = 7 ≠ dp[2][5] = 4 → 3 alınmış, c = 5 − 3 = 2; dp[2][2] = 3 ≠ dp[1][2] = 1 → 2 alınmış, c = 0.
Seçim: 2 ve 3 (ağırlık 2 + 3 = 5, değer 3 + 4 = 7).
def knapsack(items, W):
n = len(items)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i, (w, v) in enumerate(items, start=1):
for c in range(W + 1):
dp[i][c] = dp[i - 1][c]
if w <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
chosen, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i - 1][c]:
chosen.append(i)
c -= items[i - 1][0]
return dp[n][W], sorted(chosen), dp
best, chosen, dp = knapsack([(1, 1), (2, 3), (3, 4), (4, 5)], 5)
for row in dp:
print(row)
print('best value:', best, '| items:', chosen)▸ Beklenen çıktı
[0, 0, 0, 0, 0, 0] [0, 1, 1, 1, 1, 1] [0, 1, 3, 4, 4, 4] [0, 1, 3, 4, 5, 7] [0, 1, 3, 4, 5, 7] best value: 7 | items: [2, 3]
En uzun ortak alt dizi (LCS): iki metinde aynı sırayla (yan yana olması gerekmeden) geçen en uzun karakter dizisi. “ABCBDAB” ve “BDCABA” için LCS uzunluğu 4'tür, örneğin “BCBA”. LCS, diff ve git'teki dosya karşılaştırmasının ve DNA dizilerinin hizalanmasının temelidir.
- L[i][j]a'nın ilk i ve b'nin ilk j karakterinin LCS uzunluğu
- L[0][j] = L[i][0]0 (boş metinle ortak hiçbir şey yok)
Süre O(m · n): uzunluğu 1000 olan iki metin için yalnızca 10⁶ hücre gerekir, oysa tüm alt dizileri denemek 2¹⁰⁰⁰ seçenek demektir.
def lcs(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
out, i, j = [], len(a), len(b)
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return dp[-1][-1], ''.join(reversed(out))
print(lcs('ABCBDAB', 'BDCABA'))
print(lcs('AGGTAB', 'GXTXAYB'))▸ Beklenen çıktı
(4, 'BCBA') (4, 'GTAB')
Açgözlü mü, DP mi?
Açgözlü algoritma her adımda o an en iyi görünen seçimi yapar ve asla geri dönmez. Hızlı ve basittir ama yalnızca “açgözlü seçim özelliği” olan problemlerde doğrudur: Kruskal, Dijkstra, Huffman kodlaması, kesirli sırt çantası. DP ise tüm seçenekleri tekrarsız karşılaştırır ve en iyi alt yapı ile örtüşen alt problemlerin olduğu her yerde doğru cevabı verir.
- coins[x]x tutarını oluşturan en az bozuk para sayısı
- ckullanılabilir bir bozuk para değeri
Bozuk paralar {1, 3, 4}, tutar 6. Açgözlü algoritma (her zaman en büyük para) kaç para kullanır? En iyi cevap nedir?
Çözümü gösterÇözümü gizle
DP tablosu coins[0 … 6]:
coins[1] = 1, coins[2] = 2, coins[3] = 1, coins[4] = 1,
coins[5] = 1 + min(coins[4], coins[2], coins[1]) = 1 + 1 = 2,
coins[6] = 1 + min(coins[5], coins[3], coins[2]) = 1 + 1 = 2.
En iyi: 2 para (3 + 3). İlk adımda “en büyüğü almak” doğru yolu kapattı.
def min_coins(coins, amount):
dp = [0] + [float('inf')] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount], dp
def greedy_coins(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return count
best, table = min_coins([1, 3, 4], 6)
print('greedy:', greedy_coins([1, 3, 4], 6), '| DP:', best, '| table:', table)
print('greedy:', greedy_coins([1, 5, 6, 9], 11), '| DP:', min_coins([1, 5, 6, 9], 11)[0])▸ Beklenen çıktı
greedy: 3 | DP: 2 | table: [0, 1, 2, 1, 1, 2, 2] greedy: 3 | DP: 2
| Yaklaşım | Fikir | Ne zaman doğru | Örnek |
|---|---|---|---|
| Böl ve yönet | bağımsız alt problemler | alt problemler tekrarlanmadığında | birleştirmeli sıralama |
| Dinamik programlama | tekrarlanan alt problemlerin cevaplarını sakla | en iyi alt yapı + örtüşen alt problemler | sırt çantası, LCS, paralar |
| Açgözlü | her zaman yerel olarak en iyi seçim | açgözlü seçim özelliği kanıtlandığında | Kruskal, Dijkstra, Huffman kodlaması |
Önemli noktalar
- Özyinelemenin bir temel durumu ve ona yaklaşan bir adımı olmalıdır; her çağrı yığıtta bir çerçeve kaplar.
- Basit özyinelemeli Fibonacci Θ(φⁿ), bellekleme ya da tabloyla O(n)'dir.
- DP koşulları: en iyi alt yapı ve örtüşen alt problemler; tarif: durum, geçiş, temel, sıra.
- 0/1 sırt çantası O(nW), LCS O(mn)'dir; çözüm tablodan geriye yürüyerek geri kurulur.
- Açgözlü algoritma hızlıdır ama yalnızca açgözlü seçim özelliği varsa en iyidir ({1, 3, 4} ile 6: 3 değil 2 para).
Kendini test et
10 soru. Her doğru cevap XP kazandırır.