• Örtüşen Alt Problemler (Overlapping Subproblems): Bu, bir problemin optimal çözümünün, aynı alt problemlerin tekrar tekrar çözülmesini gerektirdiği anlamına gelir. DP, bu alt problemlerin çözümlerini saklayarak (memoization veya tabulation) tekrar hesaplama yükünü ortadan kaldırır.
• Optimal Alt Yapı (Optimal Substructure): Bir problemin optimal çözümünün, alt problemlerinin optimal çözümlerinden inşa edilebileceği anlamına gelir. Bu özellik, DP'nin uygulanabilirliği için kritik öneme sahiptir.

• Memoization (Yukarıdan Aşağı Yaklaşım): Genellikle özyinelemeli (recursive) bir fonksiyonla başlarız. Her alt problemin çözümü hesaplandığında, bir depolama yapısında (genellikle bir dizi veya hashmap) saklanır. Fonksiyon tekrar çağrıldığında, önce bu depolama yapısına bakılır; eğer çözüm zaten varsa kullanılır, yoksa hesaplanır ve saklanır.
• Tabulation (Aşağıdan Yukarı Yaklaşım): Bu yaklaşımda, alt problemlerin çözümleri en küçükten büyüğe doğru, genellikle döngüler kullanarak iteratif bir şekilde hesaplanır ve bir tabloda depolanır. Büyük problemin çözümü, tablonun en son elemanında bulunur. Bu genellikle daha az yığın alanı (stack space) kullanır ve bazı durumlarda daha verimli olabilir.

Dinamik Programlama, "Akıllı Hesap Tekrarı" prensibine dayanır. Aynı hesaplamayı defalarca yapmak yerine, sonuçları saklayıp tekrar kullanırız.

Genişletmek için tıkla ...

• Fibonacci Dizisi
• Knapsack Problemi (Sırt Çantası Problemi)
• Longest Common Subsequence (En Uzun Ortak Alt Dizi)
• Edit Distance (Levenshtein Distance)
• Coin Change (Para Üstü Problemi)
• Matrix Chain Multiplication (Matris Çarpım Zincirleme)
• Shortest Path Problems (Dijkstra, Floyd-Warshall - belli koşullarda)
• Rod Cutting (Çubuk Kesme Problemi)

function fibonacci_dp(n):
    if n <= 1:
        return n
    
    dp = array of size (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]
        
    return dp[n]

` değeri, kendisinden önceki iki değeri kullanarak hesaplanır ve bir daha hesaplanmak zorunda kalmaz. Bu, `O` zaman karmaşıklığı sağlar.

Örnek: 0/1 Knapsack Problemi
Belirli bir kapasiteye sahip bir sırt çantasına, her birinin belirli bir ağırlığı ve değeri olan öğelerden en yüksek toplam değeri alacak şekilde hangi öğelerin konulacağını seçme problemidir. Her öğe ya tamamen alınır ya da hiç alınmaz (0/1). Bu problem, iki boyutlu bir `dp[j]` tablosu kullanılarak çözülür; burada `i` öğe sayısı ve `j` mevcut kapasitedir.
`dp[j]` = ilk `i` öğe kullanılarak `j` kapasite ile elde edilebilecek maksimum değer.

Kod:

function knapsack_dp(weights, values, capacity):
    n = length of weights
    dp = 2D array of size (n + 1) x (capacity + 1), initialized with zeros

    for i from 1 to n:
        for w from 1 to capacity:
            if weights[i-1] <= w:  // Mevcut öğe sırt çantasına sığıyorsa
                // Öğeyi almayı seçebiliriz veya seçmeyebiliriz
                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])
            else:  // Mevcut öğe sırt çantasına sığmıyorsa
                dp[i][w] = dp[i-1][w]
                
    return dp[n][capacity]

Bu çözüm, her alt problemi bir kez hesaplayıp sonuçları saklayarak optimal çözüme ulaşır. Zaman karmaşıklığı `O(n * capacity)`'dir.

Dinamik Programlamaya Yaklaşım Adımları:
[list type="1"]
[*] Problemin optimal alt yapıya sahip olup olmadığını ve örtüşen alt problemler içerip içermediğini belirleyin.
[*] Problemin durumlarını (state) tanımlayın. DP tablosundaki her hücre neyi temsil edecek?
[*] Başlangıç durumlarını (base cases) belirleyin.
[*] Durum geçişlerini (state transitions) yazın. Yani, bir üst durumun değeri nasıl alt durumların değerlerinden türetilir?
[*] Memoization (yukarıdan aşağı) veya Tabulation (aşağıdan yukarı) yaklaşımlarından birini seçin ve algoritmayı uygulayın.
[*] Sonucu döndürün.
[/list]

Avantajları ve Dezavantajları:
Avantajları:

• Üstel zaman karmaşıklığına sahip problemleri polinom zamana düşürebilir.
• Optimal çözümü garantiler (eğer problem uygunsa).
• Tekrarlayan hesaplamaları ortadan kaldırarak performansı artırır.

Dezavantajları:

• Her problem DP ile çözülemez; optimal alt yapı ve örtüşen alt problemler gereklidir.
• Büyük durum uzaylarına sahip problemlerde bellek kullanımı yüksek olabilir.
• İlk başta anlaşılması ve uygulanması zor olabilir; özellikle durumların tanımlanması ve geçiş denklemlerinin oluşturulması bazen sezgisel olmayabilir.

Gerçek Dünya Uygulamaları:
DP, birçok pratik alanda kullanılır:

• Biyoinformatik: DNA dizi hizalaması (örneğin Smith-Waterman algoritması).
• Yapay Zeka: Doğal dil işleme (NLP) ve konuşma tanıma.
• Finans: Portföy optimizasyonu.
• Bilgisayar Grafikleri: Görüntü işleme algoritmaları.
• Ağ Yönlendirme: En kısa yol bulma.
• Kaynak Planlama: Lojistik ve tedarik zinciri yönetimi.

Sonuç:
Dinamik Programlama, karmaşık optimizasyon problemlerini çözmek için bir güçlü araçtır. Anlaşılması ve ustalaşması biraz zaman alsa da, bir kez kavrandığında algoritmik düşünce yeteneğinizi önemli ölçüde geliştirebilir. Başarıya ulaşmak için problemleri küçük parçalara ayırma, desenleri tanıma ve alt çözümleri akıllıca kullanma becerisi esastır. Bu prensipleri kavradıkça, karşılaştığınız zorlu algoritmik bulmacaların üstesinden gelmeniz çok daha kolay olacaktır. Daha fazla bilgi ve pratik yapmak için GeeksforGeeks Dinamik Programlama gibi kaynaklara başvurabilirsiniz. Bu tür platformlar, farklı zorluk seviyelerinde çok sayıda örnek problem sunar. Unutmayın, pratik yapmak mükemmelleştirir!