2D DP masalalari: jadval yo'llari, LCS, tahrir masofasi va 0/1 knapsack

Qisqacha: Masalada ikkita o'zgaruvchan narsa bo'lsa — ikki satr, xarita qatori va ustuni, taomlar soni va byudjet — DP holati ikki son bilan yoziladi: dp[i][j]. Bunda javoblar jadvalga yoziladi, har katak qo'shni kataklardan hisoblanadi. Jadval yo'llari, eng uzun umumiy qism ketma-ketlik (LCS), tahrir masofasi va 0/1 knapsack — shu naqshning to'rt klassik masalasi. Hammasi O(n · m) vaqtda ishlaydi, xotirani esa ko'pincha ikki qatorgacha qisqartirsa bo'ladi.

Bu darsda

• Masalada holat nechta son bilan aniqlanishini topasiz va 2D jadvalni qog'ozda chizib, uni to'ldirish tartibini tanlaysiz.
• Jadval yo'llari, tahrir masofasi va LCS ni yozasiz, har katak qayerdan kelishini tushuntira olasiz.
• 0/1 knapsack bilan byudjetga eng yaxshi to'plamni topasiz va tanlangan narsalarni jadvaldan orqaga yurib tiklaysiz.
• O(n · m) ni o'lchov bilan tasdiqlaysiz va jadval xotirasini ikki qatorgacha qisqartirasiz.

Oldin bilishingiz kerak: 1D DP masalalari, Tabulation va xotirani tejash, Dinamik dasturlash g'oyasi va memoization, Matritsa bilan ishlash.

1. Nega bu kerak?

Bu hafta «Bahor»da uchta savol to'plandi.

Birinchisi kuryerdan. Oshxonadan mijozgacha shahar ko'chalari to'r kabi: kuryer faqat sharqqa va janubga yuradi. Ikki chorrahada ta'mir ketyapti. Jasur aka so'radi: "Nechta har xil yo'l bor? Biri yopilsa, boshqasi qolarmikan?"

Ikkinchisi saytdan keldi. Mijoz qidiruvga lagmon deb yozdi — apostrofsiz. Menyuda esa lag'mon. Qidiruv hech narsa topmadi va mijoz ketib qoldi. Sardor o'yladi: "Ikki so'z qanchalik o'xshash ekanini qanday o'lchash mumkin?"

Uchinchisi — mehmon Dilshod akadan. Byudjeti 100 000 so'm, har taomni bir martadan oladi va eng mazali to'plamni xohlaydi. Asosiy murakkablik sinflari darsida bunday masalani hamma to'plamlarni sanab yechgan edik — O(2ⁿ). Menyuda 40 ta taom bo'lsa, bu trillionlab to'plam.

Uchala masala bir xil ko'rinishga ega: javob ikki o'zgaruvchiga bog'liq. 1D DP masalalari darsida holat bitta son edi: "i-kungacha eng yaxshi natija". Bugun holat ikki son bo'ladi va javoblar qatori jadvalga aylanadi. Bu xuddi Excel jadvali: har katakdagi formula qo'shni kataklarga qaraydi.

2. Jadvalni chizib fikrlash

2.1 Holat ikki son bilan

Eslaylik: dinamik dasturlashda katta masala kichik masalalarga bo'linadi, har biri bir marta hisoblanadi va jadvalga yoziladi. Holat — kichik masalani to'liq tasvirlaydigan qiymatlar. Memoization'da ikki sonli holat kaliti ${i},${j} edi. Tabulation'da esa u 2D jadvalning katagi bo'ladi.

Bugungi masalalarda bitta son yetmaydi:

Ikki son bo'lgani uchun javoblar to'g'ri to'rtburchak jadvalga tushadi. Masala o'lchamlari n va m bo'lsa, jadval (n + 1) × (m + 1) katak.

2.2 Besh savol

2D masalani kodga o'tkazishdan oldin qog'ozga jadval chizing va besh savolga javob bering:

1. Holat: dp[i][j] aniq nimani bildiradi? Bir gap bilan yozing.
2. O'tish: katak qaysi qo'shnilardan hisoblanadi? Odatda tepa, chap va chap-tepa diagonal.
3. Asos (base case): birinchi qator va birinchi ustunga nima yoziladi? Bu — bo'sh satr, nol byudjet kabi holatlar.
4. Tartib: katak hisoblanayotganda uning qo'shnilari allaqachon tayyormi? Ko'pincha qatorma-qator, chapdan o'ngga.
5. Javob: jadvalning qaysi katagida? Ko'pincha o'ng pastki burchakda.

Qog'ozdagi 4 × 5 jadvalni qo'lda to'ldirish besh daqiqa oladi. Lekin aynan shu besh daqiqa kodda kechaning yarmini oladigan xatoning oldini oladi. Endi besh savolni to'rt masalaga qo'llaymiz.

3. Jadval yo'llari: kuryer marshruti

3.1 Sodda yechim: hamma yo'llarni sanash

Har chorrahada kuryerning ikki tanlovi bor: pastga yoki o'ngga. Rekursiya buni to'g'ridan-to'g'ri yozadi: "bu yerdan yo'llar = pastdan yo'llar + o'ngdan yo'llar". Hozircha ta'mirsiz, n × n shaharni olamiz:

let calls = 0;
function countPathsSlow(rows, cols, r = 0, c = 0) {
  calls++;
  if (r >= rows || c >= cols) return 0; // shahardan chiqdi
  if (r === rows - 1 && c === cols - 1) return 1; // yetib keldi
  return countPathsSlow(rows, cols, r + 1, c) +
    countPathsSlow(rows, cols, r, c + 1);
}

for (const n of [8, 10, 12, 14]) {
  calls = 0;
  const paths = countPathsSlow(n, n);
  console.log(`${n}×${n}: ${paths} yo'l, ${calls} chaqiruv`);
}

Konsolda:

8×8: 3432 yo'l, 18875 chaqiruv
10×10: 48620 yo'l, 272271 chaqiruv
12×12: 705432 yo'l, 3997447 chaqiruv
14×14: 10400600 yo'l, 59431999 chaqiruv

Shahar har safar ikki qatorga kattalashdi — chaqiruvlar har safar 14–15 baravar oshdi. Bu eksponensial o'sish. 14 × 14 shaharda bor-yo'g'i 196 ta chorraha, lekin 59 million chaqiruv. Demak, bitta chorraha o'rtacha 300 mingdan ortiq marta qayta hisoblandi.

3.2 G'oya: har chorrahaga necha yo'l kelishini yozish

Teskari savol beramiz: "(r, c) chorrahaga nechta yo'l keladi?" Kuryer bu yerga faqat ikki joydan keladi: tepadan yoki chapdan. Demak:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Asos — boshlanish nuqtasi: dp[0][0] = 1. Ta'mirdagi chorrahaga yo'l yo'q: 0. Chetda qo'shni yo'q bo'lsa, uni 0 deb olamiz. Tartib: qatorma-qator, chapdan o'ngga — shunda tepa va chap qo'shni doim tayyor bo'ladi.

function countPaths(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp = Array.from({ length: rows }, () =>
    Array(cols).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) continue; // ta'mir
      if (r === 0 && c === 0) {
        dp[r][c] = 1; // boshlanish
        continue;
      }
      const fromTop = r > 0 ? dp[r - 1][c] : 0;
      const fromLeft = c > 0 ? dp[r][c - 1] : 0;
      dp[r][c] = fromTop + fromLeft;
    }
  }
  return dp[rows - 1][cols - 1];
}

const grid = [
  [0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0],
];
console.log(countPaths(grid)); // 7

grid da 1 — ta'mirdagi chorraha, 0 — ochiq. Jadval qanday to'lishini qadamma-qadam kuzating. Har qadamda sariq kataklar — formula qaragan qo'shnilar:

Kuzatgan bo'lsangiz, birinchi qator va birinchi ustun to'liq 1 lardan iborat. U yerga faqat bitta yo'l bor: to'g'ri o'ngga yoki to'g'ri pastga. Ta'mirdagi chorrahadan keyingi kataklar faqat bitta qo'shnidan yig'adi.

3.3 Murakkablik

Har katak bir marta hisoblanadi, har birida O(1) ish. Jadvalda rows × cols katak, shuning uchun vaqt O(rows · cols), xotira ham shuncha. 14 × 14 shaharda 59 million chaqiruv o'rniga 196 qadam. 1000 × 1000 shahar ham bir zumda hisoblanadi.

Xotirani Tabulation va xotirani tejash darsidagi usul bilan qisqartirish mumkin. Har katakka faqat tepasi va chapi kerak, ya'ni oldingi qator. Demak, bitta qatorni saqlab, uni joyida yangilasa bo'ladi: O(cols) xotira.

Tekshirib ko'ring: 3 × 3 shaharda ta'mir yo'q. O'ng pastki burchakka nechta yo'l bor? Jadvalni qog'ozda to'ldiring.

4. Tahrir masofasi: "lagmon" va "lag'mon"

4.1 Uch amal

Tahrir masofasi (edit distance) — bir satrni ikkinchisiga aylantirish uchun kerak bo'ladigan eng kam tahrirlar soni. Tahrir uch xil bo'ladi: bitta harfni qo'shish, o'chirish yoki almashtirish. Bu o'lchovni 1965-yilda sovet matematigi Vladimir Levenshtein taklif qilgan, shuning uchun uni Levenshtein masofasi ham deyishadi.

Misollar: lagmon → lag'mon — bitta qo'shish, masofa 1. somsa → samsa — bitta almashtirish, 1. manti → manti — 0. Qidiruv shunday ishlashi mumkin: menyuda aynan moslik bo'lmasa, masofasi 1–2 bo'lgan taomni "Balki shuni nazarda tutgandirsiz?" deb taklif qiladi.

4.2 O'tish formulasi

Holat: dp[i][j] — a satrning birinchi i harfini b satrning birinchi j harfiga aylantirish narxi. Endi a ning i-harfi va b ning j-harfiga qaraymiz:

• Harflar teng — ularga tegmaymiz. Narx qolgan qismniki bilan bir xil: dp[i - 1][j - 1].
• Harflar har xil — uch yo'ldan eng arzonini tanlaymiz va 1 qo'shamiz:
  • a ning harfini o'chiramiz → dp[i - 1][j] (tepa katak);
  • b ning harfini qo'shamiz → dp[i][j - 1] (chap katak);
  • birini ikkinchisiga almashtiramiz → dp[i - 1][j - 1] (diagonal).

Asos holatlari — birinchi qator va ustun. Bo'sh satrdan j harfli satr yasash uchun j marta qo'shish kerak: dp[0][j] = j. i harfli satrdan bo'sh satr qilish uchun i marta o'chirish kerak: dp[i][0] = i.

4.3 Jadvalni kuzatamiz

Mijoz osh o'rniga shoshib ohs deb yozdi. Masofani kuzatamiz. Har qadamda sariq — formula qaragan kataklar:

Diqqat qiling: oxirgi katakda uchala qo'shni ham 1 edi, javob — 2. Ikki harfning o'rni almashgani Levenshtein uchun ikki tahrir hisoblanadi. O'rin almashishni bitta tahrir deb sanaydigan varianti ham bor (Damerau–Levenshtein), lekin bugun asosiy variantni o'rganamiz.

4.4 Kod va o'lchov

Vizualdagi kod — to'liq yechim. Uni turli so'zlarda sinab ko'ramiz:

function editDistance(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0));
  for (let i = 0; i <= a.length; i++) dp[i][0] = i;
  for (let j = 0; j <= b.length; j++) dp[0][j] = j;
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  return dp[a.length][b.length];
}

console.log(editDistance("lagmon", "lag'mon")); // 1
console.log(editDistance("somsa", "samsa")); // 1
console.log(editDistance("", "osh")); // 3
console.log(editDistance("kabob", "kebab")); // 2

a[i - 1] ga e'tibor bering. Jadvalda 0-qator — bo'sh satr, shuning uchun jadvalning i-qatoriga satrning (i − 1)-harfi mos keladi. Bu bitta siljish 2D DP dagi eng ko'p xatoning manbai.

Murakkablik: a uzunligi n, b uzunligi m. Jadvalda (n + 1) × (m + 1) katak, har birida O(1) ish. Vaqt — O(n · m), xotira — O(n · m). Ikkala satr ikki baravar uzaysa, vaqt to'rt baravar oshishi kerak. Tekshiramiz: urug'li generatorda yasalgan tasodifiy satrlarni benchmarking darsidagi usulda o'lchadik — har n alohida jarayonda, isitish, 7 o'lchov medianasi. Raqamlar taxminiy:

Nisbat har safar taxminan 4 — O(n · m) tasdiqlandi. Chiziqlar deyarli ustma-ust: ikki qatorli variant tezroq emas. Uning yutug'i boshqa joyda — xotirada.

4.5 Xotira: ikki qator yetadi

Formulaga yana qarang: katak faqat joriy qatorga va undan oldingi qatorga qaraydi. Demak, butun jadvalni saqlash shart emas — ikkita qator yetadi:

function editDistanceLight(a, b) {
  let prev = Array.from({ length: b.length + 1 }, (_, j) => j);
  let cur = new Array(b.length + 1);
  for (let i = 1; i <= a.length; i++) {
    cur[0] = i;
    for (let j = 1; j <= b.length; j++) {
      cur[j] = a[i - 1] === b[j - 1]
        ? prev[j - 1]
        : 1 + Math.min(prev[j], cur[j - 1], prev[j - 1]);
    }
    [prev, cur] = [cur, prev]; // qatorlar o'rnini almashtiramiz
  }
  return prev[b.length];
}

console.log(editDistanceLight("lagmon", "lag'mon")); // 1
console.log(editDistanceLight("ohs", "osh")); // 2

[prev, cur] = [cur, prev] — massiv destructuring bilan ikki o'zgaruvchining o'rnini almashtirish. Yangi qator yasalmaydi, ikki massiv navbatma-navbat ishlatiladi. Xotira — O(m).

Farq sezilarlimi? 4 000 harfli ikki satr uchun process.memoryUsage() bilan o'lchadik. To'liq jadval ≈ 130 MB oldi — 16 milliondan ortiq katak. Ikki qator esa ≈ 64 KB oldi. Taxminan ikki ming baravar kam. Telefonda 130 MB — tabning yopilishi uchun yetarli sabab.

Lekin bir narsani yo'qotamiz: to'liq jadval bo'lmasa, qaysi tahrirlar qilinganini orqaga yurib tiklab bo'lmaydi. Faqat masofa qoladi. Qidiruv takliflari uchun masofaning o'zi yetadi; git diff kabi "nima o'zgardi" kerak bo'lsa — jadval kerak.

Tekshirib ko'ring: editDistance("osh", "ash") va editDistance("non", "") nechaga teng?

5. LCS: eng uzun umumiy qism ketma-ketlik

5.1 Kechagi va bugungi menyu

Jasur aka menyuni har kuni biroz o'zgartiradi. Sardor saytga "Nima o'zgardi?" bo'limini qo'shmoqchi. Buning uchun ikki ro'yxatning umumiy qismini topish kerak. Qolgani — qo'shilgan yoki olib tashlangan taomlar.

Qism ketma-ketlik (subsequence) — ro'yxatdan ba'zi elementlarni olib tashlab, qolganlarini tartibini buzmasdan olish. [osh, lag'mon] — [osh, manti, lag'mon] ning qism ketma-ketligi. Elementlar yonma-yon turishi shart emas, faqat tartib saqlanadi. LCS (longest common subsequence) — ikki ro'yxatning eng uzun umumiy qism ketma-ketligi.

5.2 Formula va kod

Holat: dp[i][j] — a ning birinchi i ta va b ning birinchi j ta elementi uchun LCS uzunligi. O'tish:

• elementlar teng — ikkalasi LCS ga kiradi: dp[i - 1][j - 1] + 1;
• har xil — birini tashlab ko'ramiz va kattasini olamiz: max(dp[i - 1][j], dp[i][j - 1]).

Asos: bo'sh ro'yxat bilan LCS — 0 (birinchi qator va ustun). Javob — o'ng pastki katakda. LCS ning o'zini olish uchun jadvaldan orqaga yuramiz: teng elementda diagonal bo'ylab chiqamiz, bo'lmasa kattaroq qo'shni tomonga:

function lcs(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  // Umumiy ketma-ketlikni orqaga yurib yig'amiz
  const common = [];
  let i = a.length;
  let j = b.length;
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      common.push(a[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
    else j--;
  }
  return common.reverse();
}

const yesterday = ["osh", "manti", "lag'mon", "somsa", "chuchvara"];
const today = ["manti", "osh", "lag'mon", "chuchvara", "norin"];
console.log(lcs(yesterday, today));
console.log(lcs("lagmon", "lag'mon").join(""));

Konsolda:

[ 'osh', "lag'mon", 'chuchvara' ]
lagmon

Uchta taom ikkala kunda bir xil tartibda turibdi. Qolgani o'zgarish: somsa olib tashlandi, norin qo'shildi, manti esa joyini almashtirdi. Funksiya satrlar bilan ham ishlaydi: a[i] satrda ham, massivda ham bir xil ishlaydi.

Diqqat: LCS bitta bo'lmasligi mumkin. [manti, lag'mon, chuchvara] ham uzunligi 3 bo'lgan umumiy qism. Qaysi biri chiqishi orqaga yurishdagi >= ga bog'liq. Testda LCS ning o'zini emas, uzunligini tekshirish xavfsizroq.

5.3 LCS va diff

LCS — git diff ning yuragi. Ikki faylning umumiy qatorlari — o'zgarmagan qism. LCS ga kirmagan eski qatorlar - bilan, yangilari + bilan chiqadi. Haqiqiy git tezroq algoritm ishlatadi (Myers algoritmi), lekin g'oya bir xil. Bu g'oyaga Algoritmlar real frontend va backend ishida darsida qaytamiz.

Murakkablik tahrir masofasi bilan bir xil: vaqt O(n · m), xotira O(n · m). Faqat uzunlik kerak bo'lsa, ikki qator bilan O(m).

6. 0/1 knapsack: Dilshod akaning byudjeti

6.1 Masala

Har taomning narxi va bahosi bor. Baho — Dilshod aka taomni qanchalik yoqtirishi, 1 dan 10 gacha. Har taom ko'pi bilan bir marta olinadi — shuning uchun nomi 0/1: taom yo olinmaydi (0), yo bir marta olinadi (1). Byudjet 100 000 so'm. Maqsad — baholar yig'indisi eng katta to'plam.

Bu — knapsack (ryukzak) masalasi. Klassik shartda sayyoh ryukzakka sig'adigan eng qimmat narsalarni tanlaydi. Bizda ryukzak — byudjet, narsalar — taomlar.

6.2 Holat va o'tish

Holat: dp[i][w] — faqat birinchi i ta taomdan tanlab, w byudjet bilan olish mumkin bo'lgan eng katta baho. i-taom uchun ikki tanlov:

• olmaymiz — dp[i - 1][w], byudjet o'zgarmaydi;
• olamiz (narxi sig'sa) — dp[i - 1][w - narx] + baho.

Ikkalasidan kattasi — dp[i][w]. Asos: taom yo'q yoki byudjet 0 — baho 0. Narxlar 1 000 so'mga karrali, shuning uchun byudjetni ming so'mlarda o'lchaymiz: 100 000 so'm — 100 ta ustun. Aks holda jadval 100 001 ustunli bo'lardi.

const dishes = [
  { name: "osh", price: 35000, score: 9 },
  { name: "manti", price: 30000, score: 8 },
  { name: "lag'mon", price: 28000, score: 7 },
  { name: "shashlik", price: 25000, score: 6 },
  { name: "salat", price: 15000, score: 3 },
  { name: "ko'k choy", price: 5000, score: 2 },
];

function bestOrder(dishes, budget) {
  const unit = 1000; // narxlar 1000 so'mga karrali
  const cap = budget / unit;
  const n = dishes.length;
  const dp = Array.from({ length: n + 1 }, () =>
    Array(cap + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    const cost = dishes[i - 1].price / unit;
    const score = dishes[i - 1].score;
    for (let w = 0; w <= cap; w++) {
      dp[i][w] = dp[i - 1][w]; // i-taomni olmaymiz
      if (cost <= w) {
        const take = dp[i - 1][w - cost] + score; // olamiz
        dp[i][w] = Math.max(dp[i][w], take);
      }
    }
  }
  // Qaysi taomlar tanlanganini orqaga yurib topamiz
  const chosen = [];
  for (let i = n, w = cap; i > 0; i--) {
    if (dp[i][w] !== dp[i - 1][w]) {
      chosen.push(dishes[i - 1].name);
      w -= dishes[i - 1].price / unit;
    }
  }
  return { score: dp[n][cap], chosen: chosen.reverse() };
}

console.log(bestOrder(dishes, 100000));
console.log(bestOrder(dishes, 60000));

Konsolda:

{ score: 26, chosen: [ 'osh', 'manti', "lag'mon", "ko'k choy" ] }
{ score: 16, chosen: [ 'manti', 'shashlik', "ko'k choy" ] }

100 000 so'mga osh, manti, lag'mon va ko'k choy: 98 000 so'm, baho 26. Orqaga yurish qoidasi: agar dp[i][w] uning tepasidagi katakdan farq qilsa, demak i-taom olingan. Shunda byudjetdan uning narxini ayiramiz va bir qator yuqoriga chiqamiz.

6.3 Murakkablik va "psevdo-polinom" tuzog'i

n ta taom va W ta byudjet birligi — jadval (n + 1) × (W + 1). Vaqt O(n · W), xotira ham. 6 taom × 100 birlik — 606 katak. Hamma to'plamni sanash esa 2⁶ = 64 to'plam. Bu yerda farq kichik. Lekin 40 taomda: 40 × 100 = 4 000 katak va 2⁴⁰ — trilliondan ortiq to'plam.

Bir tuzoq bor: W — taomlar soni emas, byudjet qiymati. Narxlarni so'mda (1 000 ga bo'lmasdan) olsak, ustunlar 100 001 ta bo'ladi, jadval esa 1 000 baravar kattalashadi. Shuning uchun O(n · W) ni psevdo-polinom vaqt deyishadi: u kirish sonlarining kattaligiga bog'liq. Narxlarni umumiy birlikka (1 000 so'm) bo'lish — amaliy yechim.

Xotirani bu yerda ham qisqartirsa bo'ladi: har qator faqat oldingi qatorga qaraydi. Bitta massiv bilan ishlash uchun esa w ni teskari tartibda (kattadan kichikka) aylantirish kerak. Nega shunday — "Ko'p uchraydigan xatolar" bo'limida ko'ramiz.

Tekshirib ko'ring: Byudjet 35 000 so'm. Eng katta baho nechaga teng? Avval o'zingiz o'ylang, keyin bestOrder(dishes, 35000) bilan tekshiring.

7. Chegaraviy holatlar

2D DP da chegaraviy holatlar ko'pincha jadvalning chetida yashaydi:

• Bo'sh kirish. editDistance("", "osh") — 3, lcs([], today) — []. Birinchi qator va ustun to'g'ri to'ldirilgan bo'lsa, alohida if kerak emas.
• Bitta element. 1 × 1 shahar: countPaths([[0]]) — 1 (kuryer allaqachon joyida).
• Boshlanish yopiq. countPaths([[1]]) — 0, chunki continue tufayli dp[0][0] 0 bo'lib qoladi. Tekshirib ko'ring.
• Bir xil kirish. editDistance(s, s) — doim 0, lcs(s, s) — s ning o'zi. Testlarda qulay tekshiruv.
• Narx byudjetdan katta. Knapsack bunday taomni hech qachon olmaydi — cost <= w sharti.
• Byudjet 0 yoki taom yo'q. Javob 0 — jadval nollar bilan boshlanadi.

8. Ko'p uchraydigan xatolar

8.1 Bitta qator nusxasi bilan jadval yasash

const dp = Array(3).fill(Array(3).fill(0)); // ❌
dp[0][0] = 1;
console.log(dp); // [ [ 1, 0, 0 ], [ 1, 0, 0 ], [ 1, 0, 0 ] ]

fill bitta massivni uch joyga qo'ydi — uchala qator bitta obyekt (Havola semantikasi). Bitta katakni o'zgartirsangiz, hamma qatorda o'zgaradi. Xato xabari chiqmaydi, javob esa jim noto'g'ri bo'ladi. Tuzatish: Array.from({ length: rows }, () => Array(cols).fill(0)) — har qator uchun funksiya yangi massiv yasaydi.

8.2 Indeks siljishi

Jadval satrdan bitta katta: 0-qator — bo'sh satr. a[i] o'rniga a[i - 1] yozish esdan chiqsa, birinchi harf hech qachon solishtirilmaydi, oxirida esa undefined chiqadi. Tuzatish: holat ta'rifini izohda yozing: "dp[i][j] — a ning birinchi i harfi".

8.3 Chetlarni unutish

Tahrir masofasida birinchi qator va ustun 0 bilan qolsa, editDistance("", "osh") 0 qaytaradi — bo'sh satr "osh" ga teng bo'lib qoladi. Tuzatish: besh savoldan uchinchisi — asos — doim alohida to'ldiriladi.

8.4 Knapsack'ni bitta massivda to'g'ri tartibda aylantirish

Bitta massivda w ni 0 dan yuqoriga aylantirsangiz, dp[w - cost] allaqachon shu taom bilan yangilangan bo'ladi. Natijada bitta taom ikki-uch marta olinadi. Bu boshqa masala — "cheksiz knapsack". Tuzatish: bitta massivda w ni kattadan kichikka aylantiring yoki ikki massiv ishlating. 3-mashqdagi yechim ikkinchi yo'lni tanlagan.

9. Mashqlar

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

Tahrir masofasi uchun jadvalni qog'ozda chizing: a = osh, b = ash. Birinchi qator: 0, 1, 2, 3. O'ng pastki katakdagi javob: [:1]. Keyin LCS jadvalini chizing: a = manti, b = mantu. Eng uzun umumiy qismning uzunligi: [:4].

2-mashq (o'rta): Eng tez yetkazish

Shahar xaritasidagi har chorrahada kuryer qancha daqiqa turishi ma'lum (svetofor, tirbandlik). U faqat o'ngga va pastga yuradi. Funksiya minDeliveryTime(minutes) chap yuqoridan o'ng pastgacha eng kam umumiy vaqtni qaytarsin. Ishora: bu safar yo'llar qo'shilmaydi — tepa va chapdan kichigi tanlanadi va katakning o'z vaqti qo'shiladi. Birinchi qator va ustunda tanlov yo'q.

function minDeliveryTime(minutes) {
  const rows = minutes.length;
  const cols = minutes[0].length;
  const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const here = minutes[r][c];
      if (r === 0 && c === 0) dp[r][c] = here;
      else if (r === 0) dp[r][c] = dp[r][c - 1] + here;
      else if (c === 0) dp[r][c] = dp[r - 1][c] + here;
      else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + here;
    }
  }
  return dp[rows - 1][cols - 1];
}

const minutes = [
  [1, 3, 1, 2],
  [1, 5, 1, 4],
  [4, 2, 1, 1],
];
console.log(minDeliveryTime(minutes)); // 8
console.log(minDeliveryTime([[7]])); // 7

3-mashq (qiyin): Knapsack'ni to'liq tanlov bilan tekshiring

kurs/mashqlar/14/53-2d-dp/knapsack.test.mjs faylida ikkita funksiya yozing. bestScore(items, cap) — ikki massivli DP (items — { cost, score } lar, cost butun son). bestScoreSlow(items, cap) — hamma to'plamlarni rekursiya bilan ko'radigan sodda yechim. Testlar:

1. «Bahor» menyusi (narxlar ming so'mda), byudjet 100 — 26.
2. Chegaraviy: bo'sh menyu, byudjet 0, byudjetdan qimmat taom — hammasi 0.
3. Urug'li generator bilan 200 ta tasodifiy kichik menyu: DP javobi to'liq tanlovniki bilan bir xil. Generator — Asosiy murakkablik sinflari darsidagi makeRandom.

// kurs/mashqlar/14/53-2d-dp/knapsack.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function bestScore(items, cap) {
  let prev = Array(cap + 1).fill(0);
  for (const { cost, score } of items) {
    const cur = [...prev];
    for (let w = cost; w <= cap; w++) {
      cur[w] = Math.max(prev[w], prev[w - cost] + score);
    }
    prev = cur;
  }
  return prev[cap];
}

function bestScoreSlow(items, cap, i = 0) {
  if (i === items.length) return 0;
  const skip = bestScoreSlow(items, cap, i + 1);
  if (items[i].cost > cap) return skip;
  const take = items[i].score +
    bestScoreSlow(items, cap - items[i].cost, i + 1);
  return Math.max(skip, take);
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

test("«Bahor» menyusi: 100 ming so'mga 26 ball", () => {
  const items = [
    { cost: 35, score: 9 }, { cost: 30, score: 8 },
    { cost: 28, score: 7 }, { cost: 25, score: 6 },
    { cost: 15, score: 3 }, { cost: 5, score: 2 },
  ];
  assert.equal(bestScore(items, 100), 26);
});

test("chegaraviy: bo'sh menyu, nol byudjet, qimmat taom", () => {
  assert.equal(bestScore([], 50), 0);
  assert.equal(bestScore([{ cost: 5, score: 2 }], 0), 0);
  assert.equal(bestScore([{ cost: 60, score: 9 }], 50), 0);
});

test("200 ta tasodifiy menyuda DP = to'liq tanlov", () => {
  const random = makeRandom(54);
  const int = (lo, hi) => lo + random() % (hi - lo + 1);
  for (let k = 0; k < 200; k++) {
    const items = Array.from({ length: int(0, 10) }, () => ({
      cost: int(1, 30), score: int(1, 10),
    }));
    const cap = int(0, 60);
    assert.equal(bestScore(items, cap), bestScoreSlow(items, cap));
  }
});

✔ «Bahor» menyusi: 100 ming so'mga 26 ball (0.8158ms)
✔ chegaraviy: bo'sh menyu, nol byudjet, qimmat taom (0.1415ms)
✔ 200 ta tasodifiy menyuda DP = to'liq tanlov (3.0706ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 9.567

4-mashq: Amaliy tajriba — 2D DP qatorlari

kurs/mashqlar/14/MURAKKABLIK.md jadvaliga bugungi to'rt masalani qo'shing: kuryer yo'llari (sodda va DP), tahrir masofasi (to'liq jadval va ikki qator), LCS va 0/1 knapsack. Har biriga vaqt va xotirani yozing. Knapsack uchun "Nega" ustuniga psevdo-polinom ekanini qayd eting.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Kuryer yo'llari | rekursiya | O(2^(r+c)) | O(r + c) stek |
| Kuryer yo'llari | 2D DP | O(r · c) | O(r · c), qator bilan O(c) |
| Tahrir masofasi | 2D DP | O(n · m) | O(n · m) |
| Tahrir masofasi | ikki qator | O(n · m) | O(m) |
| LCS | 2D DP + orqaga yurish | O(n · m) | O(n · m) |
| 0/1 knapsack | 2D DP | O(n · W) | O(n · W), qator bilan O(W) |

git add 14/MURAKKABLIK.md 14/53-2d-dp
git commit -m "14/53: 2D DP — tahrir masofasi, LCS, knapsack testlari"

10. Real ishda

• Qidiruvda xatolarni kechirish. "Balki shuni nazarda tutgandirsiz?" takliflari, imlo tekshiruvchilar va noaniq qidiruv tahrir masofasiga tayanadi. Katta lug'atlarda uni har so'z uchun hisoblash qimmat, shuning uchun avval nomzodlar qisqartiriladi. Bu haqda Algoritmlar real frontend va backend ishida darsida gaplashamiz.
• Diff. git diff, GitHub'dagi o'zgarishlar ko'rinishi va matnni solishtiruvchi vositalar LCS g'oyasidan kelib chiqadi.
• Bioinformatika. DNK ketma-ketliklarini solishtirish (Needleman–Wunsch algoritmi) — tahrir masofasining "ballar" bilan varianti.
• Resurs taqsimlash. Byudjet bo'yicha reklama kanallarini tanlash, serverlarga vazifalarni joylash — knapsack ko'rinishidagi masalalar.
• Intervyu. "Unique Paths", "Edit Distance", "Longest Common Subsequence", "0/1 Knapsack" — DP savollarining eng ko'p uchraydigan to'rttasi. Intervyuda jadvalni doskaga chizish ko'pincha kodning yarmi hisoblanadi.

Xulosa

• Holat ikki son bilan aniqlansa — DP jadvali 2D bo'ladi: dp[i][j]. Avval besh savolga javob bering: holat, o'tish, asos, tartib, javob qayerda.
• Jadval yo'llari: dp[r][c] = tepa + chap. Rekursiya 14 × 14 da 59 million chaqiruv qildi, DP esa 196 qadam.
• Tahrir masofasi: teng harf — diagonal, aks holda 1 + min(tepa, chap, diagonal). O(n · m) o'lchovda tasdiqlandi: n × 2 → vaqt × 4.
• LCS: teng — diagonal + 1, aks holda max(tepa, chap); orqaga yurish umumiy qismni beradi. git diff ning g'oyasi shu.
• 0/1 knapsack: "olmaymiz" yoki "olamiz" — O(n · W), W — byudjet birliklari (psevdo-polinom).
• Faqat oldingi qator kerak bo'lsa, xotira O(m) ga tushadi: 4 000 harfda ≈ 130 MB o'rniga ≈ 64 KB. Lekin javobni tiklash uchun jadval kerak.

Keyingi dars: Greedy algoritmlar — har qadamda eng yaxshi ko'ringan tanlovni qilish. Bu ba'zan DP jadvalisiz ham to'g'ri javob beradi, ba'zan esa adashtiradi.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 14.4 (LCS), 15.2 (0/1 va kasrli knapsack — greedy bilan solishtirish).
• V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals", 1965 (ruscha asl), 1966 (inglizcha tarjima).
• MDN: Array.from(), Array.prototype.fill() — developer.mozilla.org
• LeetCode masalalari (shartlarini o'zingiz o'qing): 62 "Unique Paths", 64 "Minimum Path Sum", 72 "Edit Distance", 1143 "Longest Common Subsequence".