Tabulation va xotirani tejash: DP jadvalini pastdan yuqoriga to'ldirish

Qisqacha: Tabulation — DP javoblarini rekursiyasiz, kichik holatlardan kattasiga qarab jadvalga (massivga) yozib chiqish. Har katak to'ldirilganda unga kerakli kichik katakchalar allaqachon tayyor bo'ladi. Stek to'lmaydi, funksiya chaqiruvi va Map xarajati yo'q — qazi masalasida memo'dan taxminan 10 baravar tez chiqdi. Agar formula faqat oxirgi bir nechta qiymatga qarasa, butun jadval o'rniga ikki-uchta o'zgaruvchi yetadi: xotira O(n) dan O(1) ga tushadi.

Bu darsda

• DP masalasini besh savol bilan loyihalay olasiz: holat, formula, asos, tartib, javob qayerda.
• Memoization yechimini tabulation'ga aylantira olasiz.
• Jadvalni qaysi yo'nalishda to'ldirish kerakligini formula bo'yicha aniqlay olasiz.
• Faqat kerakli qatorlarni saqlab, xotirani O(n) dan O(1) yoki O(k) ga tushira olasiz.
• Memoization va tabulation'ni tezlik, xotira va stek bo'yicha solishtira olasiz.

Oldin bilishingiz kerak: Dinamik dasturlash g'oyasi va memoization, Xotira murakkabligi, Ikki ko'rsatkich, Sliding window.

1. Nega bu kerak?

O'tgan darsda Jasur akaning qazi masalasini memo bilan yechdik: 4 000 bo'lakli qazini 0,16 soniyada. Keyin Sardor sinab ko'rdi: ombordagi hamma qazi bir qatorga terilsa — 8 000 bo'lak. Dastur yiqildi:

RangeError: Maximum call stack size exceeded

Hisob qiyin emas edi — O(n²), 8 000 da bir necha o'n million amal. Muammo boshqa joyda: bestCut(8000) → bestCut(7999) → … → bestCut(0) — 8 000 ta chaqiruv bir vaqtda stekda kutadi. Stekka sig'madi.

Savol: kichik javoblarni olish uchun rekursiya shartmi? Javoblar baribir bestCut(0), bestCut(1), bestCut(2) … tartibida tayyor bo'ladi. Ularni o'sha tartibda o'zimiz hisoblasak-chi? Bugun shuni qilamiz.

2. Pastdan yuqoriga

2.1 G'oya

Tabulation (inglizcha "table" — jadval) yoki pastdan yuqoriga (bottom-up) DP — javoblarni eng kichik holatdan boshlab, jadvalga ketma-ket yozib borish. Har yangi katak oldingi kataklardan hisoblanadi.

Memo bilan farqi — yo'nalishda. Memo yuqoridan boshlaydi: "bestCut(8) kerak → unga bestCut(7) kerak → …" va pastga tushadi. Tabulation pastdan: "dp[0] ma'lum → dp[1] ni hisoblayman → dp[2] ni …" va yuqoriga chiqadi.

Uy qurilishiga o'xshaydi. Memo — me'mor: "tom kerak, tomga devor kerak, devorga poydevor kerak" deb rejani yuqoridan tuzadi. Tabulation — usta: poydevordan boshlab, g'ishtni g'isht ustiga qo'yadi. Usta hech qachon "tom uchun nima kerak edi?" deb o'ylamaydi — u to'g'ri tartibda quradi va har g'isht qo'yilganda ostidagisi tayyor.

2.2 Qazi jadvali

dp[i] — i bo'lakli qazidan olinadigan eng ko'p pul. Formula o'tgan darsdagi bilan bir xil, faqat funksiya chaqiruvi o'rniga massiv katagi:

dp[0] = 0
dp[i] = eng kattasi ( prices[k] + dp[i − k] ),  k = 1 … i

Quyidagi jadvalda har qator — bitta i, har ustun — birinchi bo'lak uzunligi k. Katakdagi son — nomzod: prices[k] + dp[i - k]. Oxirgi ustun — dp[i], qatordagi eng kattasi. Sariq katak — hozir o'qilayotgan dp[i - k]: u doim yuqoriroq qatorda, ya'ni allaqachon to'ldirilgan:

Kodda faqat ikkita ichma-ich sikl:

function bestCutTab(n, prices) {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    for (let k = 1; k <= Math.min(i, prices.length - 1); k++) {
      dp[i] = Math.max(dp[i], prices[k] + dp[i - k]);
    }
  }
  return dp[n];
}

const prices = [0, 8, 20, 30, 38, 48, 62, 70, 80];
console.log(bestCutTab(8, prices)); // 82
console.log(bestCutTab(20, prices)); // 8 dan uzun bo'lak sotilmaydi
const fair = Array.from({ length: 10001 }, (_, k) => k * 10);
console.log(bestCutTab(10000, fair)); // 100000 — stek muammosi yo'q

Konsolda:

82
206
100000

Ikkinchi qator: 20 bo'lak. Narxlar ro'yxatida eng uzun bo'lak — 8, shuning uchun k prices.length - 1 gacha cheklangan. Javob 206: uchta 6 lik (3 × 62) va bitta 2 lik (20). Uchinchi qator — 10 000 bo'lak, rekursiyasiz, bir zumda. Narxlar adolatli (har bo'lak 10 ming) bo'lgani uchun javob 100 000.

2.3 Murakkablik

Vaqt — memo bilan bir xil: tashqi sikl n marta, ichki sikl — i marta. Jami n(n + 1) ÷ 2 = O(n²). Xotira — dp massivi, O(n). Lekin rekursiya steki yo'q — chuqurlik muammosi butunlay yo'qoldi.

O'lchadik (urug'li narxlar jadvali; har n alohida jarayonda, 7 o'lchov medianasi — benchmarking usuli; raqamlar taxminiy):

Ikkalasi ham O(n²): n ikki baravar — vaqt to'rt baravar (tabulation'da aniq ×3,9–4,0). Lekin tabulation 10–14 baravar tez. Sababi — o'zgarmas ko'paytuvchi: memo har qadamda funksiya chaqiradi, Map dan has va get qiladi. Tabulation esa massiv katagini indeks bilan o'qiydi — protsessor uchun eng arzon amal. Big-O bu farqni ko'rsatmaydi, o'lchov ko'rsatadi.

3. DP'ni loyihalash: besh savol

Tabulation yozishdan oldin besh savolga javob bering. Javoblar bo'lsa, kod o'zi chiqadi.

1. Holat nima? dp[i] nimani bildiradi — bir gap bilan, aniq. "i bo'lakli qazidan eng ko'p pul". Gap noaniq bo'lsa, formula ham noaniq bo'ladi.
2. O'tish formulasi qanday? dp[i] qaysi kichik holatlardan va qanday hisoblanadi.
3. Asos nima? Formulasiz ma'lum bo'lgan kataklar: dp[0] = 0.
4. Tartib qanday? Har katak hisoblanganda formula o'qiydigan kataklar tayyor bo'lishi kerak.
5. Javob qayerda? Ko'pincha dp[n], ba'zan butun jadvalning eng kattasi (buni keyingi darsda ko'ramiz).

Birinchi savol eng muhimi. Ko'p xato aynan shu yerda: "dp[i] — i gacha bo'lgan nimadir" kabi tuman ta'rif bilan formula yozib bo'lmaydi.

Tekshirib ko'ring: Qazi jadvalida dp uzunligi nega n + 1, n emas?

4. Jadval yo'nalishi

Qazi formulasida dp[i] faqat kichik indekslarga qaraydi (dp[i - k], k ≥ 1). Shuning uchun chapdan o'ngga (0 dan n gacha) to'ldiramiz.

Ba'zi masalalarda formula katta indekslarga qaraydi. Masalan, «Bahor» kassasida savol shunday: "i-kundan oxirgi kungacha eng ko'p qancha bonus yig'ish mumkin?" Bugungi javob ertangi va indinga javobdan quriladi: best[i] kelajakdagi best[i + 1] va best[i + 2] ga bog'liq. Unda jadval o'ngdan chapga to'ldiriladi: avval best[n] (oxirgi kun — asos), keyin best[n - 1], … best[0] (javob).

Qoida bitta: formula qaysi kataklarga qarasa, ular avval to'ldirilsin. Formulani yozib, strelkalarni chizing: dp[i] dan u o'qiydigan kataklarga. Hamma strelka chapga qarasa — chapdan o'ngga to'ldiring. O'ngga qarasa — o'ngdan chapga.

Bu Topologik saralash darsidagi g'oyaning o'zi! DP holatlari — tugunlar, "bu katak shu katakka kerak" — strelkalar. Graf siklsiz bo'lishi shart (aks holda holat o'z-o'ziga bog'liq — formula ma'nosiz). To'ldirish tartibi — topologik tartib. Memo bu tartibni rekursiya bilan avtomatik topadi. Tabulation'da uni siz tanlaysiz.

5. Xotirani tejash

5.1 Hamma katak kerakmi?

«Bahor» yangi bonus tizimini sinab ko'rmoqda. Mijoz n ming so'mlik bonusni 1 ming va 2 ming so'mlik kuponlar bilan tartibli ishlatishi mumkin (masalan, 3 ming: 1+1+1, 1+2, 2+1). Necha xil usul bor? Oxirgi kupon 1 ming bo'lsa — qolgan n − 1 ni ishlatish usullari; 2 ming bo'lsa — n − 2 niki. Demak, dp[i] = dp[i - 1] + dp[i - 2] — Fibonachchi formulasi.

Usullar soni juda tez o'sadi — 78 ming so'mdayoq Number.MAX_SAFE_INTEGER dan oshadi. Shuning uchun bunday masalalarda javob odatda katta tub son bo'yicha qoldiq bilan so'raladi (modul arifmetikasi): % 1_000_000_007.

To'liq jadval O(n) xotira oladi. Lekin formulaga qarang: dp[i] faqat oxirgi ikkita katakka qaraydi. dp[i - 3] va undan oldingilari hech qachon qayta o'qilmaydi. Ularni saqlash — ortiqcha.

5.2 Ikki o'zgaruvchi

Butun massiv o'rniga ikkita o'zgaruvchi: prev (dp[i - 2]) va cur (dp[i - 1]). Har qadamda yangi qiymatni hisoblab, ikkalasini bir pog'ona suramiz. Quyida massiv faqat tushuntirish uchun chizilgan — kodda u yo'q. Ramkaga (oynaga) qarang: bir vaqtda faqat ikkita katak "tirik":

Bu Sliding window darsidagi oyna g'oyasi: o'lchami o'zgarmas oyna massiv bo'ylab suriladi. Xotira — O(1): n qancha bo'lmasin, ikkita son.

5.3 O'lchov: xotira

Massivli va ikki o'zgaruvchili versiyalarning qo'shimcha xotirasini o'lchadik (--expose-gc, process.memoryUsage().heapUsed farqi — Xotira murakkabligi darsidagi usul):

Massiv har son uchun 8 bayt oldi, n bilan birga chiziqli o'sdi. Ikki o'zgaruvchi — o'lchab bo'lmaydigan darajada kichik. Javob ikkalasida bir xil (masalan, n = 8 000 000 da 484 970 415).

5.4 Umumiy qoida: oxirgi k ta

Formula oxirgi k ta katakka qarasa, k ta katak yetadi — O(k) xotira. Buni ikki usulda yozish mumkin:

• Bir nechta o'zgaruvchi (prev, cur) — k = 2 yoki 3 bo'lsa qulay.
• Aylanma massiv — k o'lchamli massiv va indeks i % k. Bu Queue darsidagi ring buffer bilan bir xil g'oya. 2-mashqda shunday qilasiz.

Qazi masalasida esa bu ishlamaydi: dp[i] hamma oldingi kataklarga qaraydi (k = 1 … i). Hammasi kerak — O(n) xotira qoladi. Xotirani tejash — har DP uchun emas, faqat formula "qisqa xotirali" bo'lganda.

2D jadvallarda (ikkita indeksli holat) xuddi shu g'oya qatorlar bilan ishlaydi: formula faqat oldingi qatorga qarasa, butun jadval o'rniga ikkita qator saqlanadi. Buni 2D DP darsida ko'ramiz.

Tekshirib ko'ring: Kuponlar 1, 2 va 5 ming so'mlik bo'lsa, formula qanday bo'ladi va nechta o'zgaruvchi kerak?

6. Memoization yoki tabulation?

To'rtinchi qator memo'ning yagona, lekin ba'zan muhim ustunligi. Ba'zi masalalarda ko'p holatlar umuman kerak bo'lmaydi. Masalan, savol shunday: 50 000 so'mni 10 000 lik va 25 000 lik kupyuralar bilan to'lash mumkinmi? Memo faqat 50 000, 40 000, 25 000 kabi bir nechta summaga tushadi. Tabulation esa 0 dan 50 000 gacha hammasini hisoblaydi.

Amaliy yo'l: avval memo bilan to'g'ri yechim yozing (o'ylash oson), keyin kerak bo'lsa tabulation'ga aylantiring (tezlik, stek, xotira). Intervyuda ham ko'pincha shunday so'rashadi: "Endi rekursiyasiz yozing."

7. Chegaraviy holatlar

• n = 0. new Array(1) — bitta katak, sikl ishlamaydi, javob dp[0]. Asosni sikldan oldin to'g'ri qo'ying.
• "Imkonsiz" holatlar. Ba'zi holatlarga umuman yetib bo'lmaydi (masalan, 3 ming so'mni faqat 2 minglik kupon bilan). Ularni 0 bilan to'ldirsangiz, "0 so'm" va "imkonsiz" aralashib ketadi. Eng kichigi so'ralsa — Infinity, eng kattasi so'ralsa — -Infinity bilan boshlang (keyingi dars, coin change).
• Manfiy indeks. dp[i - k] da i - k < 0 bo'lsa, dp[-1] — undefined. Sikl chegarasini k <= i bilan cheklang.
• Juda katta sonlar. Usullar soni tez o'sadi — % MOD ni har qo'shishdan keyin qiling, oxirida emas. Aks holda oraliq qiymat aniqligini yo'qotadi.
• O(1) versiyada asos. n <= 1 ni sikldan oldin alohida qaytaring — aks holda n = 0 da ham cur (1) qaytadi.

8. Ko'p uchraydigan xatolar

8.1 Noto'g'ri tartib

for (let i = n; i >= 1; i--) — qazi jadvalini o'ngdan chapga to'ldirish. dp[i - k] hali 0 — natija noto'g'ri, xato xabari esa yo'q. Tuzatish: formulaning strelkalarini chizing va tartibni ularga moslang.

8.2 Surishda qiymatni yo'qotish

prev = cur;
cur = prev + cur; // ❌ prev allaqachon yangilangan

Ikkinchi qatorda prev endi cur ga teng — natija 2 × cur. Tuzatish: avval yangi qiymatni vaqtinchalik o'zgaruvchiga hisoblang (next), keyin suring. Yoki massiv destructuring: [prev, cur] = [cur, prev + cur] — o'ng tomon to'liq hisoblanib, keyin tayinlanadi.

8.3 Jadval o'lchamida adashish

new Array(n) — dp[n] uchun joy yo'q. Tuzatish: holatlar 0 … n bo'lsa — n + 1 katak.

8.4 fill bilan ichma-ich massiv

2D jadvalda new Array(rows).fill(new Array(cols).fill(0)) — hamma qator bitta massiv! Bitta katakni o'zgartirsangiz, butun ustun o'zgaradi. Tuzatish: Array.from({ length: rows }, () => new Array(cols).fill(0)) — har qator yangi massiv (Havola semantikasi).

9. Mashqlar

1-mashq (oson): Jadvalni qo'lda to'ldiring

Narxlar: 1 bo'lak — 3, 2 — 7, 3 — 9 (ming so'm), boshqa uzunlik sotilmaydi. dp[0] … dp[5] ni to'ldiring. 5 bo'lakni qanday kesish kerak?

2-mashq (o'rta): Faqat uch katak

Endi qazi faqat 1, 2 yoki 3 bo'lak qilib sotiladi. bestCutMax3(n, prices) ni O(1) xotira bilan yozing. Ishora: formula oxirgi 3 ta katakka qaraydi — 4 ta katakli aylanma massiv va i % 4 indeks.

function bestCutMax3(n, prices) { // faqat 1, 2, 3 bo'lak sotiladi
  const dp = [0, 0, 0, 0]; // dp[i % 4] — 4 ta katak yetadi
  for (let i = 1; i <= n; i++) {
    let best = 0;
    for (let k = 1; k <= Math.min(3, i); k++) {
      best = Math.max(best, prices[k] + dp[(i - k) % 4]);
    }
    dp[i % 4] = best;
  }
  return dp[n % 4];
}
console.log(bestCutMax3(8, [0, 8, 20, 30])); // 80
console.log(bestCutMax3(1_000_000, [0, 8, 20, 30])); // 10000000

3-mashq (qiyin): Memo va jadval — testda

kurs/mashqlar/14/51-tabulation/tab.test.mjs faylida memo va tabulation versiyalarini yozing. Testlar (node:test):

1. n = 0 va n = 1.
2. n = 0 … 60 uchun ikkala versiya bir xil javob beradi.
3. n = 20 000 da memo RangeError bilan yiqiladi, tabulation esa to'g'ri javob beradi.

Ishora: xato turini kutish — assert.throws(() => ..., RangeError).

// kurs/mashqlar/14/51-tabulation/tab.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

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 <= Math.min(n, prices.length - 1); k++) {
      best = Math.max(best, prices[k] + go(n - k));
    }
    memo.set(n, best);
    return best;
  }
  return go(n);
}

function bestCutTab(n, prices) {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    for (let k = 1; k <= Math.min(i, prices.length - 1); k++) {
      dp[i] = Math.max(dp[i], prices[k] + dp[i - k]);
    }
  }
  return dp[n];
}

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

test("n = 0 va n = 1", () => {
  assert.equal(bestCutTab(0, prices), 0);
  assert.equal(bestCutTab(1, prices), 8);
});

test("memo va tabulation 0..60 da bir xil", () => {
  for (let n = 0; n <= 60; n++) {
    const fast = bestCutTab(n, prices);
    assert.equal(fast, bestCutMemo(n, prices), `n=${n}`);
  }
});

test("n = 20 000: memo yiqiladi, jadval ishlaydi", () => {
  assert.throws(() => bestCutMemo(20_000, prices), RangeError);
  // 3333 ta 6 lik (62) + bitta 2 lik (20)
  assert.equal(bestCutTab(20_000, prices), 206_666);
});

✔ n = 0 va n = 1 (0.7258ms)
✔ memo va tabulation 0..60 da bir xil (2.1796ms)
✔ n = 20 000: memo yiqiladi, jadval ishlaydi (4.4994ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 84.8725

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: qazi (tabulation), bonus usullari (massiv va ikki o'zgaruvchi), 1–3 bo'lakli qazi (aylanma massiv).

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Qazi kesish | tabulation | O(n²) | O(n) |
| Bonus usullari (fib) | dp massivi | O(n) | O(n) |
| Bonus usullari (fib) | ikki o'zgaruvchi | O(n) | O(1) |
| Qazi, bo'lak ≤ 3 | aylanma massiv i % 4 | O(n) | O(1) |

git add 14/MURAKKABLIK.md 14/51-tabulation
git commit -m "14/51: tabulation — jadval, O(1) xotira va testlar"

10. Real ishda

• Ishlab chiqarish kodi. Kutubxonalardagi DP algoritmlari (masalan, matnlar farqini topish) deyarli doim tabulation bilan yoziladi: stekka ishonib bo'lmaydi — kirish hajmi foydalanuvchiga bog'liq.
• Xotira cheklangan muhit. Telefon brauzerida yoki kichik serverda katta jadval xotirani to'ldiradi. "Faqat oxirgi qator" hiylasi ko'p hollarda O(n · m) xotirani O(m) ga tushiradi.
• Elektron jadvallar. Excel'dagi "har katak yuqoridagi katakdan hisoblanadi" (masalan, jamg'arma hisobi) — tabulation'ning kundalik ko'rinishi. Excel ham kataklarni bog'liqlik tartibida qayta hisoblaydi.
• Intervyu. Odatiy ketma-ketlik: brute force → memo → tabulation → xotirani tejash. Har bosqichda murakkablikni aytish kerak. Oxirgi qadam ("O(1) xotira bilan qila olasizmi?") — kuchli nomzodni ajratadigan savol.

Xulosa

• Tabulation — javoblarni kichik holatdan kattasiga, rekursiyasiz jadvalga yozish. Stek muammosi yo'q: 16 000 bo'lak ham ishladi.
• Besh savol: holat, formula, asos, tartib, javob qayerda. Holatni bir gap bilan aniq yozing.
• Tartib formulaga bog'liq: dp[i] kichik indekslarga qarasa — chapdan o'ngga, kattalariga — o'ngdan chapga. Bu topologik tartib.
• Bir xil O(n²), lekin tabulation memo'dan 10–14 baravar tez chiqdi — o'zgarmas ko'paytuvchi farqi.
• Formula oxirgi k ta katakka qarasa — O(k) xotira: bonus usullarida 61 MB → ≈ 0.

Keyingi dars: 1D DP masalalari — zinapoya, "qo'shni kunlarda emas" aksiyasi (house robber), qaytim (coin change), eng uzun o'suvchi ketma-ketlik va so'zlarga bo'lish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 14.1 (bottom-up rod cutting), 14.3 (kichik masalalar grafi).
• Steven S. Skiena, "The Algorithm Design Manual", 3-nashr, Springer, 2020 — 10-bob (dinamik dasturlash).
• Node.js hujjatlari: process.memoryUsage() — nodejs.org/api/process.html