Karmaşık problemleri alt problemlere bölerek ve sonuçları saklayarak çözen teknik.
Temel Özellikler
- Örtüşen Alt Problemler: Aynı alt problemler tekrar çözülür
- Optimal Alt Yapı: Optimal çözüm, alt problemlerin optimal çözümlerinden oluşur
Yaklaşımlar
1. Memoization (Top-Down)
Özyinelemeli çözümde sonuçları saklar.
FONKSİYON Fibonacci_Memo(n, memo)
EĞER (n <= 1) DÖNDÜR n
EĞER (memo[n] tanımlı) DÖNDÜR memo[n]
memo[n] = Fibonacci_Memo(n-1, memo) + Fibonacci_Memo(n-2, memo)
DÖNDÜR memo[n]
SON
2. Tabulation (Bottom-Up)
Alt problemlerden başlayarak yukarı doğru çözer.
FONKSİYON Fibonacci_Tab(n)
EĞER (n <= 1) DÖNDÜR n
dp[0] = 0, dp[1] = 1
TEKRARLA (i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2]
DÖNDÜR dp[n]
SON
Kullanım Alanları
- Fibonacci sayıları
- Sırt çantası problemi
- En uzun ortak alt dizi
- Para üstü problemi
- Matris zincir çarpımı
Avantajları
- Üssel zaman karmaşıklığını polinom zamana düşürür
- Optimal çözümü garanti eder
- Alt problemlerin tekrar hesaplanmasını önler