Dinamik Programlama Nedir?
İngilizce: Dynamic Programming
Yayın: · Son güncelleme:
Dinamik Programlama Nedir? Kısaca
Dinamik programlama, büyük bir problemi örtüşen alt problemlere bölüp her alt problemi yalnız bir kez çözen ve sonucunu saklayan bir algoritma tasarım yöntemidir. Tekrarlanan hesapları ortadan kaldırarak çözümü çok hızlandırır.
Dinamik programlama nedir?
Dinamik programlama, aynı hesabı tekrar tekrar yapmamak için ara sonuçları kaydeden bir problem çözme yöntemidir. Adındaki "programlama" kelimesi kod yazmayı değil, planlama ve tablo kurma anlamını taşır. 1950'lerde matematikçi Richard Bellman tarafından geliştirilmiştir.
Nasıl çalışır?
Bir problem dinamik programlamaya uygunsa iki özellik taşır. Büyük problemin çözümü küçük alt problemlerin çözümünden kurulabilir. Aynı alt problemler de hesap sırasında defalarca karşınıza çıkar. Yöntem, her alt problemi bir kez çözüp sonucu bir tabloya ya da sözlüğe yazar.
Fibonacci dizisi bunun klasik örneğidir. Her sayı önceki iki sayının toplamıdır. 40. sayıyı düz özyineleme ile hesaplarsanız, aynı küçük değerler milyonlarca kez yeniden hesaplanır. Sonuçları saklarsanız her değer bir kez hesaplanır ve iş 40 civarı adımda biter.
İki uygulama yolu
Yukarıdan aşağı yöntemde (memoization) fonksiyon özyinelemeli yazılır, ama her sonuç bir önbellekte tutulur. Fonksiyon aynı girdiyle tekrar çağrılırsa önbellekten cevap verir. Python'da functools.lru_cache bu işi tek satırla yapar.
Aşağıdan yukarı yöntemde (tablolama) en küçük alt problemden başlanır ve tablo sırayla doldurulur. Fibonacci için önce 0 ve 1 yazılır, sonra her yeni değer önceki iki değerin toplamı olarak eklenir. Bu yaklaşım özyineleme kullanmadığı için yığın taşması riski taşımaz.
Nerelerde kullanılır?
En kısa yol bulma, bozuk para ile para üstü verme, sırt çantası problemi ve iki metin arasındaki farkı hesaplama gibi problemler dinamik programlamayla çözülür. Git gibi araçların dosya farklarını göstermesi de benzer algoritmalara dayanır. Mülakat hazırlığı yapıyorsanız, Fibonacci ile başlayıp para üstü problemine geçmek iyi bir sıralamadır.
Sıkça Sorulan Sorular
Memoization ne demek?
Memoization, bir fonksiyonun daha önce hesapladığı sonuçları saklayıp aynı girdiyle yeniden çağrıldığında hesap yapmadan saklanan sonucu döndürmesidir. Dinamik programlamanın yukarıdan aşağı uygulanış biçimidir.
Dinamik programlama ile böl ve yönet arasındaki fark nedir?
Böl ve yönet yönteminde alt problemler birbirinden bağımsızdır. Dinamik programlamada ise alt problemler örtüşür, yani aynı alt problem defalarca karşınıza çıkar ve sonucu saklamak bu yüzden işe yarar.