Bu ders için video bulunmamaktadır.
Bu derse başlamak veya ilerlemenizi kaydetmek için lütfen giriş yapın veya kayıt olun.
Ders İçeriği
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