Dinamik Programlama

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.

• 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ı.

• 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.

• 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.

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.