Dinamik dasturlash g'oyasi va memoization: kichik masalalarni bir marta yechish

Qisqacha: Dinamik dasturlash (DP) — katta masalani kichik masalalarga bo'lib, har kichik masalani bir marta yechib, javobini saqlash usuli. U ikki shart bajarilganda ishlaydi: kichik masalalar qayta-qayta uchraydi (ustma-ust tushadi) va katta masalaning eng yaxshi javobi kichiklarning eng yaxshi javoblaridan quriladi (optimal quyi tuzilma). Rekursiv yechimga kesh qo'shish — memoization (yuqoridan pastga DP) — eksponensial vaqtni polinomialga tushiradi: qazi kesish masalasida 2ⁿ chaqiruv n²/2 ga aylandi.

Bu darsda

• Rekursiv yechimda takrorlanadigan kichik masalalarni topa olasiz.
• Dinamik dasturlashning ikki shartini tushuntira olasiz: ustma-ust tushadigan kichik masalalar va optimal quyi tuzilma.
• Masala uchun holat va rekursiv formulani yozib, unga memo qo'sha olasiz.
• Memoization murakkabligini "holatlar soni × bitta holat narxi" bilan hisoblay olasiz va o'lchov bilan tasdiqlay olasiz.

Oldin bilishingiz kerak: Memoization, Backtracking chuqur va kesish, Rekursiv fikrlash, Kodning murakkabligini hisoblash.

1. Nega bu kerak?

Jasur aka «Bahor»da qazi ham sotadi. Qazi uzun bo'lib tayyorlanadi, mijozlar esa turli uzunlikda olishadi. Uzunlikni "bo'lak" bilan o'lchaymiz (bir bo'lak — 10 sm). Narxlar uzunlikka to'g'ri proporsional emas: ba'zi o'lchamlar talabgir, ba'zilari kamroq.

Narxlar (ming so'm): 1 bo'lak — 8, 2 — 20, 3 — 30, 4 — 38, 5 — 48, 6 — 62, 7 — 70, 8 — 80.

Jasur akaning savoli: "8 bo'laklik qazini qanday kesib sotsam, eng ko'p pul olaman?" Butunligicha sotsa — 80 ming. To'rtta 2 lik qilib sotsa — 4 × 20 = 80. 6 + 2 qilsa — 62 + 20 = 82! Qaysi biri eng yaxshi? Variantlar ko'p, ularni qanday tez tekshirish kerak?

Nomi haqida bir og'iz. "Dinamik dasturlash" nomini 1950-yillarda matematik Richard Bellman qo'ygan. O'sha paytda "programming" so'zi "kod yozish" emas, "reja tuzish" ma'nosida ishlatilgan. Shuning uchun nomdan ko'p ma'no qidirmang: DP — bu "javoblar jadvalini rejali to'ldirish".

Bu darsga ikkita va'da bor. Memoization darsida keshlangan fib haqida: "bu usulning algoritmlardagi nomi — yuqoridan pastga dinamik dasturlash". Kodning murakkabligini hisoblash darsida esa fib daraxtida bir xil chaqiruvlar qayta hisoblanishini ko'rdik. Bugun shu g'oyani har qanday masalaga qo'llash retseptini olamiz.

2. Takrorlanadigan kichik masalalar

2.1 fib ni eslaymiz

Avval tanish misol. Quyida fib(5) ning chaqiruvlar daraxti: har tugun — bitta chaqiruv. Avval memosiz versiyaga qarang va bir xil chaqiruvlarni sanang, keyin memo bilan qanday "kesilishini" ko'ring:

Memosiz versiyada 15 ta chaqiruvdan faqat 6 tasi turli: f(0) dan f(5) gacha. Qolganlari — takror. Bu takrorlar daraxt bilan birga eksponensial o'sadi: fib(30) da 2,7 million chaqiruv, turli qiymatlar esa 31 ta.

2.2 Ustma-ust tushadigan kichik masalalar

Masala o'zining kichikroq nusxalariga bo'linadi — buni Rekursiv fikrlash darsida o'rgandik. Bo'lib-yech (Divide and conquer) usulida kichik masalalar mustaqil edi: merge sort chap va o'ng yarimni alohida saralaydi, ular hech qachon bir xil bo'lagini qayta ishlamaydi.

fib da esa boshqacha. fib(5) ning ikki shoxi — fib(4) va fib(3). fib(4) ning ichida yana fib(3) bor. Shoxlar umumiy kichik masalalarga ega. Buni ustma-ust tushadigan kichik masalalar (overlapping subproblems) deyishadi.

Bu oshxonadagi zirvakka o'xshaydi. Uchta qozonda osh damlash kerak. Har qozon uchun alohida zirvak qovurish — uch baravar ish. Aqlli oshpaz katta qozonda bir marta qovurib, uchga bo'ladi. Bir xil ishni bir marta qilib, natijani qayta ishlatadi.

3. Qazi masalasi

3.1 Holat va formula

Endi Jasur akaning masalasi. Uni kichikroq nusxaga bo'lishni o'ylaymiz. n bo'laklik qazidan birinchi kesiladigan bo'lakni tanlaymiz: uzunligi k (1 dan n gacha). U prices[k] so'mga sotiladi. Qolgan n − k bo'lak — yana o'sha masala, faqat kichikroq!

bestCut(n) — n bo'laklik qazidan olinadigan eng ko'p pul. Unda:

bestCut(0) = 0
bestCut(n) = eng kattasi ( prices[k] + bestCut(n − k) ),  k = 1 … n

Bu yerda ikkita yangi so'z bor. Holat (state) — kichik masalani to'liq tasvirlaydigan qiymatlar to'plami. Bu masalada holat bitta son: n — qazi uzunligi. O'tish formulasi (recurrence) — holat javobini kichikroq holatlar javobi orqali ifodalaydigan qoida. Yuqoridagi ikkinchi qator — aynan shu. Birinchi qator — asos (base case): rekursiya qayerda to'xtashi.

3.2 Sodda rekursiya

Formulani to'g'ridan-to'g'ri kodga ko'chiramiz va chaqiruvlarni sanaymiz:

const prices = [0, 8, 20, 30, 38, 48, 62, 70, 80]; // ming so'm

let calls = 0;
function bestCut(n) {
  calls++;
  if (n === 0) return 0;
  let best = 0;
  for (let k = 1; k <= n; k++) {
    best = Math.max(best, prices[k] + bestCut(n - k));
  }
  return best;
}

for (const n of [4, 5, 6, 7, 8]) {
  calls = 0;
  const result = bestCut(n);
  console.log(`n=${n}: ${result} ming so'm, ${calls} chaqiruv`);
}

Konsolda:

n=4: 40 ming so'm, 16 chaqiruv
n=5: 50 ming so'm, 32 chaqiruv
n=6: 62 ming so'm, 64 chaqiruv
n=7: 70 ming so'm, 128 chaqiruv
n=8: 82 ming so'm, 256 chaqiruv

Javoblar to'g'ri: 8 bo'lakdan 82 ming — 6 + 2 kesish. 4 bo'lakdan 40 ming (2 + 2), butunligicha sotishdan (38) qimmat. Lekin chaqiruvlar soniga qarang: har bo'lak qo'shilganda ikki baravar. Aniq formula — 2ⁿ. Nega? bestCut(n) o'zidan kichik hamma holatlarni chaqiradi: bestCut(n - 1), bestCut(n - 2), …, bestCut(0). bestCut(n - 1) esa yana hammasini. Bu backtracking kabi hamma kesish usulini sinash — n bo'lakli qazini 2ⁿ⁻¹ xil usulda kesish mumkin.

O'lchadik (benchmarking usuli: har n alohida jarayonda, mediana; raqamlar taxminiy):

Har bo'lak vaqtni taxminan ikki baravar oshirdi: 6 → 13 → 24 → 51 → 100 ms. 24 bo'lakda 0,1 soniya, 34 bo'lakda — taxminan 100 soniya, 44 bo'lakda — bir sutkadan ko'p. Bu O(2ⁿ) — eksponensial o'sish.

3.3 Qayerda takror?

bestCut(8) ichida bestCut(5) necha marta chaqiriladi? Birinchi bo'lak 3 bo'lsa — bir marta. Birinchi ikkita bo'lak 1 va 2 bo'lsa — yana. 2 va 1 bo'lsa — yana. 1, 1, 1 bo'lsa — yana. Lekin 5 bo'lakli qazining eng yaxshi narxi har safar bir xil — 50 ming! U qanday yo'l bilan "qolgani" ahamiyatsiz. Biz uni to'rt marta qayta hisobladik.

Faqat 9 ta turli holat bor: bestCut(0) … bestCut(8). 256 chaqiruvning qolgani — takror. fib dagi manzaraning o'zi.

4. Optimal quyi tuzilma

4.1 Ikkinchi shart

Takror bo'lishi yetarli emas. DP ishlashi uchun yana bir shart kerak: katta masalaning eng yaxshi javobi kichik masalalarning eng yaxshi javoblaridan qurilishi kerak.

Qazida shunday. 8 bo'lakdan eng yaxshi kesish birinchi bo'lak 2 bilan boshlansa, qolgan 6 bo'lak ham eng yaxshi usulda kesilgan bo'lishi shart. Aks holda qolgan 6 bo'lakni yaxshiroq kesib, umumiy pulni oshirgan bo'lardik — demak, boshlang'ich "eng yaxshi" emas edi. Bu optimal quyi tuzilma (optimal substructure) deyiladi.

Siz bu mulohazani allaqachon ko'rgansiz: Eng qisqa yo'l darsida "eng qisqa yo'lning har bo'lagi ham eng qisqa yo'l" degan edik. Dijkstra ham aslida shu xususiyatdan foydalanadi.

4.2 Qachon bajarilmaydi

Har masalada bu xususiyat yo'q. Masalan: "grafda ikki tugun orasidagi eng uzun oddiy (tugunlari takrorlanmaydigan) yo'l". A dan C ga eng uzun yo'l B orqali o'tsa, uning A → B bo'lagi A dan B ga eng uzun yo'l bo'lishi shart emas. A → B eng uzun yo'li C ni ham bosib o'tishi mumkin — keyin C ga qaytib bo'lmaydi, tugun takrorlanadi. Kichik masalalarning eng yaxshi javoblari bir-biriga xalaqit beradi. Bu masala uchun samarali DP ma'lum emas.

Shuning uchun DP'ni qo'llashdan oldin ikki savol beriladi:

1. Kichik masalalar takrorlanadimi? (Yo'q bo'lsa — oddiy rekursiya yoki bo'lib-yech yetarli.)
2. Eng yaxshi javob kichiklarning eng yaxshisidan quriladimi? (Yo'q bo'lsa — DP noto'g'ri javob beradi.)

Tekshirib ko'ring: Merge sort'da kichik masalalar takrorlanadimi? Nega u DP emas?

5. Memoization — yuqoridan pastga DP

5.1 Kesh qo'shamiz

Endi yechim aniq: har holat javobini birinchi hisoblaganda saqlaymiz, keyingi safar tayyorini qaytaramiz. Rekursiv funksiyaga kesh qo'shish — memoization (Memoization darsida universal memoize yozgan edik). DP tilida bu yuqoridan pastga (top-down) usul: katta masaladan (bestCut(8)) boshlab, kerakli kichiklarga tushamiz.

Quyida 4 bo'lakli qazi. Massiv — memo holati: i-katak — bestCut(i) javobi (? — hali noma'lum). Stek — hali tugamagan chaqiruvlar. Uchinchi qadamdan keyin "yana so'raldi" degan qadamlarga e'tibor bering — ular bitta qadamda tugaydi:

Endi sakkiz bo'lakda ham sinaymiz. Memo har chaqiruvda yangi bo'lishi uchun funksiyani "zavod" ichiga o'raymiz (closure):

const prices = [0, 8, 20, 30, 38, 48, 62, 70, 80]; // ming so'm

function makeBestCut(prices) {
  const memo = new Map();
  let calls = 0;
  function bestCut(n) {
    calls++;
    if (n === 0) return 0;
    if (memo.has(n)) return memo.get(n);
    let best = 0;
    for (let k = 1; k <= n; k++) {
      best = Math.max(best, prices[k] + bestCut(n - k));
    }
    memo.set(n, best);
    return best;
  }
  return { bestCut, callCount: () => calls };
}

for (const n of [4, 8]) {
  const { bestCut, callCount } = makeBestCut(prices);
  const result = bestCut(n);
  console.log(`n=${n}: ${result} ming so'm, ${callCount()} chaqiruv`);
}

Konsolda:

n=4: 40 ming so'm, 11 chaqiruv
n=8: 82 ming so'm, 37 chaqiruv

256 chaqiruv o'rniga 37. Javob o'zgarmadi.

5.2 Murakkablikni hisoblash

Memoization murakkabligini hisoblashning oddiy retsepti bor:

vaqt = holatlar soni × bitta holatni hisoblash narxi (rekursiv chaqiruvlarni hisobga olmasdan — ular keshdan keladi).

Qazi uchun: holatlar — n + 1 ta (0 … n). Bitta holat — k bo'yicha sikl, n tagacha qadam. Jami: O(n²). Aniqrog'i, sikl qadamlari 1 + 2 + … + n = n(n + 1) ÷ 2. n = 8 da 36 — chaqiruvlar soni esa 37 (+1 — birinchi chaqiruvning o'zi).

Xotira: memo — O(n) ta qiymat. Rekursiya chuqurligi ham O(n): bestCut(n) → bestCut(n - 1) → … → bestCut(0). Bu chuqurlik bitta muammoga olib keladi — pastroqda ko'ramiz.

fib uchun retsept: holatlar — n + 1, bitta holat — bitta qo'shish, O(1). Jami O(n) — Kodning murakkabligini hisoblash darsidagi natija.

5.3 O'lchov

Memo versiyasini o'lchadik (urug'li narxlar jadvali; har n alohida jarayonda, mediana):

n ikki baravar — vaqt taxminan to'rt baravar (va biroz ko'proq: katta Map va chuqur stek protsessor keshiga sig'maydi). O(n²) tasdiqlandi. Solishtiring: memosiz versiya 24 bo'lakda 0,1 soniya ishladi. Memo versiyasi 4 000 bo'lakni 0,16 soniyada yechdi.

Endi muammo. 8 000 bo'lakda memo versiyasi yiqildi:

RangeError: Maximum call stack size exceeded

Tarjimasi: "chaqiruvlar stekining eng katta hajmidan oshib ketdi". Hisob emas, rekursiya chuqurligi muammo — 8 000 ta kutayotgan chaqiruv stekka sig'madi (bizda 7 000 da hali ishladi). Buni keyingi darsda hal qilamiz: jadvalni pastdan yuqoriga, rekursiyasiz to'ldiramiz.

6. DP retsepti

Har DP masalasi uchun bir xil qadamlar:

1. Brute force rekursiyani yozing. To'g'ri ishlasa yetarli, tezligi muhim emas.
2. Holatni aniqlang. Rekursiv funksiya argumentlari — holat. Ular qanchalik kam va kichik bo'lsa, shuncha yaxshi.
3. Takrorni tekshiring. Bir xil argument bilan chaqiruv qayta uchraydimi? Kichik n uchun chaqiruvlar daraxtini chizing yoki hisoblagich qo'ying.
4. Optimal quyi tuzilmani tekshiring. Eng yaxshi javob kichiklarning eng yaxshisidan quriladimi?
5. Memo qo'shing. Kalit — holat. Funksiya toza bo'lsin: natija faqat argumentlarga bog'liq (Memoization darsidagi qoida).
6. Murakkablikni hisoblang: holatlar × bitta holat narxi.

Holat bir nechta son bo'lsa (masalan, ikki matn ichidagi ikkita indeks), kalit — ularning birikmasi: `${i},${j}` kabi. Bunday masalalarni 2D DP darsida ko'ramiz.

7. Chegaraviy holatlar

• n = 0. Asos shart birinchi turishi kerak. Bo'sh qazi — 0 so'm, prices[0] ga murojaat yo'q.
• Narxlar jadvali qisqa. prices[k] faqat k ≤ jadval uzunligi uchun bor. 10 bo'lakli qazi va 8 ta narx bo'lsa, prices[9] — undefined, undefined + 50 — NaN. Siklni Math.min(n, prices.length - 1) gacha cheklang.
• Kesh funksiya chaqiruvlari orasida qolib ketishi. Global memo bitta narxlar jadvali uchun to'g'ri. Narxlar o'zgarsa, eski javoblar noto'g'ri bo'lib qoladi. Shuning uchun darsda memo funksiya ichida yaratildi.
• Chuqur rekursiya. Holatlar zanjiri uzun bo'lsa (bizda ~7 000 dan ortiq), RangeError. Yechim — tabulation.
• Hamma narx teng ulushli. Narx uzunlikka to'liq proporsional bo'lsa, har qanday kesish bir xil pul beradi — javob bitta, kesish usullari ko'p.

8. Ko'p uchraydigan xatolar

8.1 Memoni tashqaridan o'rash

const fast = memoize(bestCut) — ichki rekursiv chaqiruvlar baribir asl, keshsiz bestCut ga boradi. Faqat eng tashqi chaqiruv keshlanadi. Tuzatish: memo tekshiruvi funksiyaning ichida bo'lsin (Memoization darsidagi "Rekursiyani tashqaridan o'rash" tuzog'i).

8.2 Holatga keraksiz narsa qo'shish

bestCut(n, cutsSoFar) — "hozirgacha qilingan kesishlar" ro'yxati ham argumentda. Endi har chaqiruv turli kalitga ega, kesh hech qachon ishlamaydi. Tuzatish: holatga faqat kelajak javobiga ta'sir qiladigan narsalarni qo'ying. Qolgan qazi uzunligi — ta'sir qiladi; qanday kesib kelganingiz — yo'q.

8.3 memo.get(n) ni || bilan tekshirish

return memo.get(n) || compute(n) — javob 0 bo'lsa (bestCut(0) yoki narx 0), 0 || … qayta hisoblaydi. Tuzatish: memo.has(n) bilan tekshiring.

8.4 Optimal quyi tuzilmasiz masalaga DP

Eng uzun oddiy yo'l kabi masalada memo xato javob beradi — va xato xabari chiqmaydi. Tuzatish: DP'dan oldin "kichiklarning eng yaxshisi katta uchun ham eng yaxshimi?" savoliga javob bering. Shubha bo'lsa, kichik n uchun brute force bilan solishtiring (3-mashqdagi stress test).

9. Mashqlar

1-mashq (oson): Chaqiruvlarni sanang

Memosiz fib(6) necha marta chaqiriladi? Memo bilan-chi? Ishora: memosiz calls(n) = calls(n - 1) + calls(n - 2) + 1, calls(0) = calls(1) = 1.

2-mashq (o'rta): Qanday kesish kerak?

Jasur akaga faqat summa emas, qanday kesish ham kerak. cutPlan(n, prices) funksiyasini yozing: { total, pieces } qaytarsin. Ishora: har holat uchun qaysi k yutganini alohida choice Map da saqlang, keyin n dan boshlab choice bo'yicha bo'laklarni yig'ing.

const prices = [0, 8, 20, 30, 38, 48, 62, 70, 80];

function cutPlan(n, prices) {
  const memo = new Map(); // n -> eng yaxshi narx
  const choice = new Map(); // n -> eng yaxshi birinchi bo'lak
  function bestCut(n) {
    if (n === 0) return 0;
    if (memo.has(n)) return memo.get(n);
    let best = 0;
    for (let k = 1; k <= n; k++) {
      const value = prices[k] + bestCut(n - k);
      if (value > best) {
        best = value;
        choice.set(n, k); // shu k yutdi
      }
    }
    memo.set(n, best);
    return best;
  }
  const total = bestCut(n);
  const pieces = [];
  for (let rest = n; rest > 0; rest -= choice.get(rest)) {
    pieces.push(choice.get(rest));
  }
  return { total, pieces };
}
console.log(cutPlan(8, prices)); // { total: 82, pieces: [ 2, 6 ] }
console.log(cutPlan(5, prices)); // { total: 50, pieces: [ 2, 3 ] }

3-mashq (qiyin): Stress test bilan tekshirish

kurs/mashqlar/14/50-dp-memo/qazi.test.mjs faylida memo versiyasini (bestCutMemo) yozing va uni brute force (bestCutSlow) bilan solishtiruvchi test yozing: 200 ta tasodifiy narxlar jadvali (n ≤ 12), urug'li generator bilan. Yana: n = 0, darsdagi narxlar (4 → 40, 8 → 82) va n = 3000 (memo tez ishlashi kerak).

Ishora: urug'li generator g'oyasini Asosiy murakkablik sinflari darsidagi makeRandom dan bilasiz. Bu yerda uning boshqa mashhur varianti — mulberry32 — ishlatilgan: u Math.random() kabi 0 dan 1 gacha kasr son qaytaradi, lekin bir xil urug'da har ishga tushirishda bir xil sonlar beradi. Ichidagi bit amallarini tushunish shart emas — funksiyani tayyor holda ko'chiring.

// kurs/mashqlar/14/50-dp-memo/qazi.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

// brute force — faqat kichik n uchun
function bestCutSlow(n, prices) {
  if (n === 0) return 0;
  let best = 0;
  for (let k = 1; k <= n; k++) {
    best = Math.max(best, prices[k] + bestCutSlow(n - k, prices));
  }
  return best;
}

function bestCutMemo(n, prices) {
  const memo = new Map();
  function go(n) {
    if (n === 0) return 0;
    if (memo.has(n)) return memo.get(n);
    let best = 0;
    for (let k = 1; k <= n; k++) {
      best = Math.max(best, prices[k] + go(n - k));
    }
    memo.set(n, best);
    return best;
  }
  return go(n);
}

function seeded(seed) { // urug'li generator (mulberry32)
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

test("bo'sh qazi — 0 so'm", () => {
  assert.equal(bestCutMemo(0, [0]), 0);
});

test("darsdagi narxlar: 4 → 40, 8 → 82", () => {
  const prices = [0, 8, 20, 30, 38, 48, 62, 70, 80];
  assert.equal(bestCutMemo(4, prices), 40);
  assert.equal(bestCutMemo(8, prices), 82);
});

test("stress test: 200 ta tasodifiy narxlar jadvali", () => {
  const random = seeded(14);
  for (let round = 0; round < 200; round++) {
    const n = 1 + Math.floor(random() * 12);
    const prices = [0];
    for (let k = 1; k <= n; k++) {
      prices.push(Math.floor(random() * 50));
    }
    assert.equal(bestCutMemo(n, prices), bestCutSlow(n, prices));
  }
});

test("n = 3000 — memo bilan tez", () => {
  // narx uzunlikka proporsional: qanday kessangiz ham 30 000
  const prices = Array.from({ length: 3001 }, (_, k) => k * 10);
  assert.equal(bestCutMemo(3000, prices), 30000);
});

✔ bo'sh qazi — 0 so'm (0.7273ms)
✔ darsdagi narxlar: 4 → 40, 8 → 82 (0.1537ms)
✔ stress test: 200 ta tasodifiy narxlar jadvali (2.9001ms)
✔ n = 3000 — memo bilan tez (125.6554ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 206.99

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: qazi kesish (sodda rekursiya va memo), fib (sodda va memo). Yangi ustun qo'shing: "Holatlar" — memo nechta turli qiymat saqlaydi.

| Masala | Yechim | Vaqt | Xotira | Holatlar |
|---|---|---|---|---|
| Qazi kesish | sodda rekursiya | O(2ⁿ) | O(n) stek | — |
| Qazi kesish | memo (top-down DP) | O(n²) | O(n) | n + 1 |
| Fibonachchi | sodda rekursiya | O(2ⁿ) | O(n) stek | — |
| Fibonachchi | memo | O(n) | O(n) | n + 1 |

git add 14/MURAKKABLIK.md 14/50-dp-memo
git commit -m "14/50: DP g'oyasi — qazi kesish, memo va stress test"

10. Real ishda

• Matn muharrirlari va diff. Ikki fayl orasidagi farqni topish (git diff), imlo tekshiruvchining "balki siz … demoqchimisiz?" taklifi — DP algoritmlari (2D DP darsida).
• Narx va resurs rejalash. Qazi kabi "kesish" masalalari ishlab chiqarishda haqiqatan bor: mato, quvur, yog'och taxtalarni minimal chiqindi bilan kesish.
• Kesh — DP'ning kundalik ko'rinishi. Serverda og'ir so'rov natijasini keshlash, frontendda hisoblangan qiymatni saqlash — "bir marta hisobla, ko'p marta ishlat" g'oyasi. Masalan, vazifalar ilovasining TEXNIK-QARZ ro'yxatida bitta band bor: qidiruvda har harf yozilganda har vazifa matni qayta normallanadi. Memoization uni hal qilishi mumkin — lekin kesh xotira oladi va matn o'zgarganda eskiradi. Shuning uchun u hozircha qarz sifatida qoldirilgan.
• Intervyu. DP — eng qo'rqinchli, lekin eng ko'p so'raladigan mavzulardan. Ko'p nomzod formulani darhol yozmoqchi bo'ladi. To'g'ri yo'l — darsdagi retsept: brute force → holat → memo. Intervyuer aynan shu fikrlashni kutadi.

Xulosa

• DP — har kichik masalani bir marta yechib, javobini saqlash. Ikki shart: kichik masalalar takrorlanadi va optimal quyi tuzilma bor.
• Holat — kichik masalani tasvirlaydigan argumentlar; o'tish formulasi holat javobini kichik holatlar orqali beradi.
• Memoization (yuqoridan pastga): rekursiya + holat bo'yicha kesh. Qazi: 2ⁿ chaqiruv → n²/2; fib: O(2ⁿ) → O(n).
• Murakkablik = holatlar soni × bitta holat narxi. O'lchovda memo n ×2 da ≈ ×4 (O(n²)); sodda versiya har bo'lakda ×2.
• Memo rekursiyasi chuqur bo'lsa, stek to'ladi (bizda 8 000 bo'lakda RangeError) — buni tabulation hal qiladi.

Keyingi dars: Tabulation va xotirani tejash — DP jadvalini pastdan yuqoriga, rekursiyasiz to'ldirish, jadval yo'nalishi va O(n) xotirani O(1) ga tushirish.

Manbalar

• Richard Bellman, "Dynamic Programming", Princeton University Press, 1957 — usul va nomning kelib chiqishi.
• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 14.1 (rod cutting — qazi masalasining asl ko'rinishi), 14.3 (DP elementlari: optimal quyi tuzilma, ustma-ust kichik masalalar).