9. Dinamik dasturlash

Fikr

Dinamik dasturlash (DD) — masalani kichik qismlarga bo‘lib, har birini
bir marta yechish va natijani saqlab qo‘yish.

Ikki shart:

1. Optimal qism struktura — katta javob kichiklaridan quriladi;
2. Qismlar takrorlanadi — bir xil kichik masala qayta-qayta

uchraydi (aynan shuning uchun saqlash foyda beradi).

Zinapoya

Zinapoyada n ta zina. Bir yoki ikki qadam tashlash mumkin. Necha xil
yo‘l bor?

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])

dp[i] — i-zinaga yetishning yo‘llari soni. Bu Fibonachchi bilan bir
xil rekurrent munosabat.

DD ni qurish tartibi

1. Holatni aniqlang: dp[i] nimani anglatadi?
2. Bazani yozing: eng kichik holat javobi.
3. O‘tishni yozing: dp[i] oldingilaridan qanday olinadi?
4. Tartibni tanlang: qaysi holat oldin hisoblanishi kerak?
5. Javobni ayting: qaysi katakda turadi?

Ryukzak (0/1)

W og‘irlikka sig‘adigan eng qimmat to‘plam:

dp = [0] * (W + 1)
for ogirlik, qiymat in buyumlar:
    for w in range(W, ogirlik - 1, -1):     # teskari!
        dp[w] = max(dp[w], dp[w - ogirlik] + qiymat)
print(dp[W])

Teskari yurish muhim: aks holda bitta buyum bir necha marta olinadi.

Ikki yo‘l

Pastdan yuqoriga (sikl bilan) — tezroq va xotirani boshqarish
oson. Yuqoridan pastga (rekursiya + lru_cache) — yozish oson,
holat murakkab bo‘lganda qulay.

Xotirani tejash

dp[i] faqat dp[i-1] va dp[i-2] ga bog‘liq bo‘lsa, butun massiv
shart emas — ikkita o‘zgaruvchi yetadi.