Dinamik programlama nedir?
Adım 1/10
[5, 2, 9, 1] üzerinde merge sort: her parça tek bir değer kalana dek ortadan iki kez böl.
Fikir
Dinamik programlama iki şey doğruysa işe yarar: aynı alt problem tekrar tekrar karşına çıkıyordur ve en iyi bütün cevap, en iyi alt cevaplardan kurulur. Merge sort hiç örtüşmeyen yeni yarılara bölünür, bu yüzden sonuçları cache'e (önbellek) almak hiçbir şey kazandırmaz. Fibonacci'nin dalları ise sürekli çakışır; cache'e almak her şeyi kazandırır. Bunu Memoization (sonuçları hafızaya alma) dersinde zaten elle yaptın; DP o alışkanlığın bilinçli hali.
Gerçek hayattan örnek
Pasta menüsünün maliyetini çıkaran bir pastane. Tariflerin yarısı aynı tereyağlı kremayı kullanıyor; pasta şefi bir partisinin maliyetini bir kez hesaplıyor ve rakamı duvara asıyor. Onu kullanan her pasta, tereyağını, şekeri ve işçiliği baştan hesaplamak yerine o rakamı okuyor.
Kod
Sıra sende
Bu kod ne yazdırır?
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
return n if n < 2 else f(n - 1) + f(n - 2)
f(10)
print(f.cache_info().misses)Mini quiz
1 / 3