Dinamik programlama , büyük ve karmaşık problemleri daha küçük alt problemlere bölerek çözmeyi amaçlayan bir optimizasyon tekniğidir. Alt problemlerin çözümleri saklanarak tekrar hesaplanmalarının önüne geçilir, böylece zaman ve kaynak tasarrufu sağlanır.

Kullanım Alanları

• Bilgisayar Bilimleri - En kısa yol bulma algoritmaları (örneğin, Floyd-Warshall algoritması), dizilim hizalama, veri sıkıştırma.
• Ekonomi - Karar verme modelleri, stok kontrolü.
• Yapay Zeka - Oyun ağaçlarının değerlendirilmesi, pekiştirmeli öğrenme algoritmaları.

Temel İlkeler

• Tekrarlanan Alt Problemler - Problemin, alt problemlerin çözümlerinin çakıştığı daha küçük alt problemlere bölünebileceği anlamına gelir. Örtüşen alt problemlerin olması, bir alt problemin çözümünün başka bir alt problemin çözümünün bir parçası olduğu anlamına gelir.
• Optimal Alt Yapı - Bir problemin tam çözümünün, daha küçük alt problemlerinin çözümlerinden oluşturulabileceği anlamına gelir. Dolayısıyla, sadece problemin örtüşen alt problemlere sahip olması gerekmez, aynı zamanda alt yapının da optimal olması gerekir, böylece alt problemlerin çözümlerini tam çözümü oluşturmak için bir araya getirmenin bir yolu vardır.

Kullanılan Yöntemler

• Memoization (üstten aşağıya yaklaşım) - Çözümün özyinelemeli olarak bulunduğu bir tekniktir. Algoritma çalıştıkça, alt problemlerin çözümleri saklanır ve bir alt problemin çözümünü hesaplamaya çalışmadan önce, aynı hesaplamayı birden fazla kez yapmaktan kaçınmak için önce bu çözümün daha önce hesaplanıp hesaplanmadığını kontrol eder.
• Tabulation (aşağıdan yukarı yaklaşım) - Problemin kapsadığı üst üste binen alt problemlerin çözümleri en temel alt problemlerden başlayarak bir tabloda saklanır.

Örnek Problem: Fibonacci Dizisinin Bulunması

Fibonacci dizisi, her bir sayının kendinden önceki iki sayının toplamı olduğu sayı dizisidir. Örneğin,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Aşağıda C++ kullanılarak Fibonacci sayılarını bulmaya yönelik örnekler bulunmaktadır.

1- Memoization Yöntemiyle

#include 
using namespace std;
vector memo(n + 1, -1);
// n'inci Fibonacci sayısını bulan fonksiyon
int nthFibonacci(int n) {  
	//Temel durumları kontrol et
    if (n <= 1) {
        return n;
    }
    // Daha önce hesaplanıp hasaplanmadığını kontrol et
    if (memo[n] != -1) {
        return memo[n];
    }
    // Fibonacci sayısını bul
    // ve sonucu sakla
    memo[n] = nthFibonacciUtil(n - 1, memo) 
              + nthFibonacciUtil(n - 2, memo);
    return memo[n];
}
int main() {
    int n = 5;
    int result = nthFibonacci(n);
    cout << result << endl;
    return 0;
}

2- Tabulation Yöntemiyle

#include 
using namespace std;
vector nthFibonacci(n + 1);
nthFibonacci[0] = 0;
nthFibonacci[1] = 1;
// n tane Fibonacci sayısı bulan fonksiyon
int dp(int n){
    // Temel durumları kontrol et
    if (n <= 1)
        return n;
    for (int i = 2; i <= n; ++i){
        // Fibonacci sayılarını hesapla
        nthFibonacci[i] = nthFibonacci[i - 1] + nthFibonacci[i - 2];
    }
}
int main(){
    int n = 5;
    dp(n);
    int result = nthFibonacci[n];
    cout << result << endl;
    return 0;
}