Dinamik programlama

Kısaca: Dinamik programlama, büyük bir sorunu çakışan alt problemlere bölerek, her alt problemi yalnızca bir kez çözerek ve sonuçları saklayarak çözer.

Biraz daha ayrıntılı: Bir sorunun en iyi alt yapısı varsa ve aynı alt problemler birkaç kez ortaya çıkıyorsa yararlıdır. Üstel sayıda durumu denemek yerine bir tabloyu küçükten büyüğe alt problemlerle doldurur (aşağıdan yukarıya) ya da özyinelemeli bir çözümde ara sonuçları hatırlarsınız (memoization, yukarıdan aşağıya).

Ayrıntılı

Örnek: bozuk para verme

En az kaç…

Ayrıca bak: Memoization, Özyineleme, Algoritmalar, Büyük O gösterimi