1D DP masalalari: zinapoya, aksiya kunlari, kuponlar, o'suvchi ketma-ketlik va so'zlarga bo'lish

Qisqacha: Ko'p DP masalasi bitta naqshga tushadi: dp[i] — "i-chi joygacha (yoki i-chi joyda tugaydigan) eng yaxshi javob", va u oldingi bir nechta dp dan hisoblanadi. Zinapoya va aksiya kunlari — oxirgi ikkita holatga qaraydi (O(n) vaqt, O(1) xotira). Kuponlar (coin change) — summadan har kupon qiymatini ayirib qaraydi (O(summa × kuponlar)). Eng uzun o'suvchi ketma-ketlik — hamma oldingilarga qaraydi (O(n²), binar qidiruv bilan O(n log n)). So'zlarga bo'lish — oldingi kesish nuqtalariga.

Bu darsda

• Besh klassik 1D DP masalasida holatni, formulani va asosni yoza olasiz.
• "i-chi joygacha" va "i-chi joyda tugaydigan" holatlar farqini tushuntira olasiz.
• Kuponlar masalasida "eng kam soni" va "nechta usul" ni, tartib muhim va muhim emas holatlarini farqlay olasiz.
• Eng uzun o'suvchi ketma-ketlikni O(n²) va O(n log n) da topa olasiz va farqni o'lchay olasiz.

Oldin bilishingiz kerak: Tabulation va xotirani tejash, Dinamik dasturlash g'oyasi, Binary search variantlari, Set.

1. Nega bu kerak?

O'tgan ikki darsda DP'ning usulini o'rgandik: holat, formula, memo, jadval. Endi amaliyot. Intervyu va real ishdagi DP masalalarining katta qismi "bir o'lchamli" — holat bitta son (indeks yoki summa). Ular bir nechta naqshga bo'linadi. Naqshni tanisangiz, yangi masala "tanish" bo'lib qoladi.

Bugun «Bahor»dagi besh vaziyatni yechamiz. Har birida bir xil savollar: dp[i] nima? Formula? Asos? Javob qayerda? Murakkablik? Har masala oldingisidan bitta yangi g'oya qo'shadi.

2. Zinapoya: oxirgi qadam bo'yicha bo'lish

2.1 Masala

«Bahor» ombori ikkinchi qavatda, zinasi n pog'ona. Sardor bir qadamda 1 yoki 2 pog'ona chiqadi. Tepaga necha xil usulda chiqishi mumkin? 3 pog'onada — 3 usul: 1+1+1, 1+2, 2+1.

2.2 Yechim

Asosiy savol: oxirgi qadam qanday bo'lgan? n-pog'onaga yo (n − 1) dan 1 qadam bilan, yo (n − 2) dan 2 qadam bilan kelinadi. Bu ikki guruh kesishmaydi va hamma usulni qamraydi. Demak:

• Holat: dp[i] — i-pog'onaga chiqish usullari soni.
• Formula: dp[i] = dp[i - 1] + dp[i - 2].
• Asos: dp[0] = 1 (joyida turish — bitta "usul"), dp[1] = 1.

Bu o'tgan darsdagi bonus kuponlari masalasining o'zi. Formula faqat oxirgi ikkita katakka qaraydi — ikki o'zgaruvchi yetadi:

function climbWays(n) {
  let prev = 1; // dp[0]: 0 pog'ona — 1 usul (joyida turish)
  let cur = 1; // dp[1]: 1 pog'ona — 1 usul
  for (let i = 2; i <= n; i++) {
    [prev, cur] = [cur, prev + cur]; // dp[i] = dp[i - 1] + dp[i - 2]
  }
  return cur;
}
console.log(climbWays(1), climbWays(3), climbWays(5), climbWays(10));

Konsolda:

1 3 8 89

Vaqt O(n), xotira O(1). [prev, cur] = [cur, prev + cur] — massiv destructuring bilan surish: o'ng tomon to'liq hisoblanib, keyin tayinlanadi.

Naqsh: "nechta usulda?" savolida — oxirgi qadam bo'yicha guruhlarga bo'ling va guruhlarni qo'shing. Guruhlar kesishmasligi shart, aks holda bitta usul ikki marta sanaladi.

3. Aksiya kunlari: ol yoki o'tkazib yubor

3.1 Masala

Jasur aka haftalik aksiya rejalashtirmoqda. Har kun uchun kutilayotgan qo'shimcha tushum ma'lum (ming so'm): [6, 9, 7, 3, 8, 4]. Lekin ketma-ket ikki kun aksiya qilib bo'lmaydi — mijozlar chegirmaga o'rganib qolishadi. Qaysi kunlarni tanlasa, tushum eng ko'p bo'ladi?

Ochko'z (greedy) fikr — "hozir eng yaxshi ko'ringanini ol" (Eng qisqa yo'l darsida tanishgan edik). Eng kattasini olamiz — 9 (2-kun). Endi 1- va 3-kunlar yopiq. Qolganidan eng kattasi 8 (5-kun) — jami 17. Lekin 1-, 3- va 5-kunlar: 6 + 7 + 8 = 21. Ochko'z tanlov yutqazdi.

3.2 Yechim

Har kun uchun ikki tanlov bor:

• Bugun aksiya yo'q — kechagacha bo'lgan eng yaxshi natija o'zgarmaydi: dp[i - 1].
• Bugun aksiya bor — kecha bo'lmagan bo'lishi kerak, demak oldingi kungacha bo'lgan eng yaxshi natija plus bugungi tushum: dp[i - 2] + gain[i].

dp[i] — i-kungacha (i-kun ham kiradi) eng ko'p tushum. Formula: dp[i] = max(dp[i - 1], dp[i - 2] + gain[i]). Yana oxirgi ikkita katak — O(1) xotira:

function bestPromo(gains) {
  let before = 0; // dp[i - 2]
  let last = 0; // dp[i - 1]
  for (const g of gains) {
    // bugun aksiya yo'q (last) yoki bor (before + g)
    [before, last] = [last, Math.max(last, before + g)];
  }
  return last;
}
console.log(bestPromo([6, 9, 7, 3, 8, 4])); // 21
console.log(bestPromo([]), bestPromo([7])); // 0 7
console.log(bestPromo([7, 10])); // 10

Bu masala intervyularda House Robber ("uy o'g'risi" — ketma-ket ikki uyga kirmaydi, LeetCode 198) nomi bilan mashhur. Biz uni halol aksiya rejasi sifatida yechdik.

Naqsh: "ol yoki o'tkazib yubor" — har element uchun ikki tanlov va ularning eng kattasi. Tanlov keyingi tanlovlarni cheklasa (qo'shni kun), holat shu cheklovni hisobga oladi.

Tekshirib ko'ring: [6, 9, 7, 3, 8, 4] uchun dp qiymatlarini birma-bir yozing.

4. Kuponlar: eng kam soni va usullar soni

4.1 Eng kam kupon

«Bahor» sovg'a kuponlari chiqardi: 1, 3 va 4 ming so'mlik. Mijoz 6 ming so'mlik buyurtmani eng kam kupon bilan to'lamoqchi. Ochko'z kassir eng kattasidan boshlaydi: 4 + 1 + 1 — uchta kupon. Lekin 3 + 3 — ikkita!

Holat endi indeks emas, summa: dp[a] — a ming so'mni to'lash uchun eng kam kupon soni. Oxirgi kupon c bo'lsa, qolgan a − c ni eng kam kupon bilan to'lash kerak:

• Formula: dp[a] = min(dp[a - c] + 1), hamma c ≤ a kuponlar bo'yicha.
• Asos: dp[0] = 0.
• Imkonsiz holat: Infinity — "hali yo'l topilmagan". 0 emas! 0 "kupon kerak emas" degani, imkonsiz esa boshqa narsa.

Quyidagi jadvalda ustunlar — summa. Sariq kataklar — formula o'qiyotgan dp[a - c] lar (doim chaproqda). Pastki qator — oxirgi kupon: javobni tiklash uchun:

Murakkablik: A ta summa × k ta kupon = O(A · k) vaqt, O(A) xotira. Bu masala intervyuda Coin Change (LeetCode 322) nomi bilan mashhur.

Ochko'z usul nega ishlamadi? U "hozir eng katta kuponni olish doim to'g'ri" deb hisoblaydi. Bu ba'zi kupon tizimlarida (masalan, 1, 2, 5, 10) to'g'ri, 1, 3, 4 da esa yo'q. Qachon ochko'z usulga ishonsa bo'lishini Greedy algoritmlar darsida ko'ramiz. DP esa har doim to'g'ri — chunki hamma variantni (aqlli tarzda) ko'radi.

4.2 Nechta usul: tartib muhimmi?

Endi boshqa savol: 6 ming so'mni nechta usulda to'lash mumkin? Bu yerda ikkita savol yashiringan:

• Tartib muhim emas — {3, 3}, {1, 1, 4} kabi to'plamlar sanaladi.
• Tartib muhim — 1+1+4, 1+4+1, 4+1+1 uchta alohida usul (zinapoyadagidek).

Ikkalasining kodi deyarli bir xil — faqat sikllar tartibi boshqa:

const coupons = [1, 3, 4];

function countSets(coupons, amount) { // tartib muhim emas
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (const c of coupons) { // tashqarida — kuponlar
    for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
  }
  return ways[amount];
}

function countOrders(coupons, amount) { // tartib muhim
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (let a = 1; a <= amount; a++) { // tashqarida — summalar
    for (const c of coupons) if (c <= a) ways[a] += ways[a - c];
  }
  return ways[amount];
}
console.log(countSets(coupons, 6), countOrders(coupons, 6));

Konsolda:

4 9

To'plamlar — 4 ta: {1×6}, {1, 1, 1, 3}, {3, 3}, {1, 1, 4}. Tartibli usullar — 9 ta. Farq qayerdan? countSets da tashqi sikl kuponlar bo'yicha. Avval faqat 1 liklar bilan hamma summalar hisoblanadi, keyin 3 liklar qo'shiladi, keyin 4 liklar. Har to'plam "kichik kupondan kattasiga" tartibida faqat bir marta sanaladi. countOrders da tashqi sikl summalar bo'yicha — har summa uchun "oxirgi kupon qaysi" deb hamma kuponni sinaydi. Bu zinapoya formulasi — tartiblar sanaladi.

Diqqat: Bu farq intervyularda eng ko'p adashtiriladigan joy. Masala shartini o'qing: "kombinatsiyalar" (LeetCode 518 "Coin Change II") — kuponlar tashqarida; "ketma-ketliklar" (LeetCode 377) — summalar tashqarida.

5. Eng uzun o'suvchi ketma-ketlik

5.1 Masala

Jasur aka 8 kunlik buyurtmalar sonini ko'rmoqda: [12, 18, 9, 15, 20, 11, 22, 16]. U "o'sish tarixi" ni izlaydi: kunlar tartibini saqlagan holda, har biri oldingisidan katta bo'lgan eng uzun kunlar ketma-ketligi. Kunlar yonma-yon bo'lishi shart emas. Masalan, 12 → 15 → 20 → 22 — to'rt kun.

Bu eng uzun o'suvchi qism-ketma-ketlik (longest increasing subsequence, LIS). "Qism-ketma-ketlik" (subsequence) — ba'zi elementlarni tashlab, qolganini tartibini o'zgartirmasdan olish. "Qism-massiv" (subarray) dan farqi — elementlar yonma-yon bo'lishi shart emas.

5.2 Yangi turdagi holat

Avvalgi masalalarda dp[i] — "i gacha bo'lgan eng yaxshi". Bu yerda bunday holat ishlamaydi. "8-kungacha eng uzun ketma-ketlik 4" desak, keyingi kunni unga qo'shish mumkinmi — bilmaymiz: ketma-ketlik qaysi son bilan tugagani noma'lum.

Shuning uchun holatni o'zgartiramiz: dp[i] — aynan i-kunda tugaydigan eng uzun o'suvchi ketma-ketlik. Endi formula aniq: i-kunni oldingi har j-kunning ketma-ketligiga ulash mumkin, agar nums[j] < nums[i]:

• Formula: dp[i] = 1 + max(dp[j]), hamma j < i va nums[j] < nums[i] bo'yicha (bunday j yo'q bo'lsa — 1).
• Javob: butun dp ning eng kattasi, dp[n - 1] emas — eng uzun ketma-ketlik istalgan kunda tugashi mumkin.

Ikki ichma-ich sikl — O(n²) vaqt, O(n) xotira.

5.3 O(n log n): binar qidiruv bilan

Bu masalani tezroq yechish mumkin. G'oya: har uzunlik uchun o'suvchi ketma-ketlikning eng kichik oxirini saqlaymiz — tails massivi. Oxiri qanchalik kichik bo'lsa, keyingi son uni davom ettirishi shuncha oson.

tails doim o'sish tartibida bo'ladi. Shuning uchun har yangi son uchun binar qidiruv bilan joy topamiz — x dan kichik bo'lmagan birinchi element (lower bound). Topilgan joyga x ni yozamiz: oxirida bo'lsa — eng uzun ketma-ketlik bittaga o'sdi; o'rtada bo'lsa — o'sha uzunlik uchun kichikroq oxir topildi.

function lengthOfGrowth(nums) {
  // tails[L] — uzunligi L + 1 bo'lgan o'suvchining eng kichik oxiri
  const tails = [];
  for (const x of nums) {
    let lo = 0;
    let hi = tails.length;
    // x dan kichik bo'lmagan birinchi joy (lower bound)
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x; // yangi oxir yoki kichikroq oxir
  }
  return tails.length;
}
console.log(lengthOfGrowth([12, 18, 9, 15, 20, 11, 22, 16])); // 4

tails uzunligi — javob. Diqqat: tails ning o'zi haqiqiy ketma-ketlik bo'lishi shart emas — u faqat "har uzunlikning eng yaxshi oxiri". Har son uchun binar qidiruv — O(log n), jami O(n log n).

O'lchadik (urug'li tasodifiy kirish; har n alohida jarayonda, mediana; raqamlar taxminiy):

O(n²) versiyada n ikki baravar — vaqt to'rt baravar (×4,2, ×4,1, ×4,1). Binar qidiruvli versiyada — ikki baravardan sal ko'p (×2,0, ×2,1, ×2,1) — log n ko'paytuvchisi. Bir xil vaqtda (≈ 0,6 s) birinchisi 16 ming kunni, ikkinchisi 8 million kunni ko'rdi.

6. So'zlarga bo'lish

6.1 Masala

«Bahor» SMS orqali buyurtma qabul qiladi. Ba'zi telefonlar bo'sh joyni yo'qotadi va xabar shunday keladi: oshmantichoy. Dastur uni menyu so'zlariga bo'la oladimi? osh + manti + choy — ha. oshmant — yo'q.

6.2 Yechim

• Holat: ok[i] — matnning birinchi i harfi menyu so'zlariga to'liq bo'linadimi (true/false).
• Formula: ok[i] = true, agar shunday j bo'lsa: ok[j] rost va text.slice(j, i) — menyu so'zi. Ya'ni: "j gacha bo'linadi, j dan i gacha esa bitta so'z".
• Asos: ok[0] = true — bo'sh boshlanish.
• Javob: ok[n].

const menu = new Set([
  "osh", "manti", "choy", "ko'k", "non", "mantichoy",
]);

function canSplit(text, words) {
  const longest = Math.max(0, ...[...words].map((w) => w.length));
  const ok = new Array(text.length + 1).fill(false);
  ok[0] = true; // bo'sh boshlanish — bo'linadi
  for (let i = 1; i <= text.length; i++) {
    for (let j = Math.max(0, i - longest); j < i; j++) {
      if (ok[j] && words.has(text.slice(j, i))) {
        ok[i] = true; // text[0..i) so'zlarga bo'linadi
        break;
      }
    }
  }
  return ok[text.length];
}
console.log(canSplit("oshmantichoy", menu)); // true
console.log(canSplit("ko'kchoynon", menu)); // true
console.log(canSplit("oshmant", menu)); // false

Menyu Set da — has O(1) (so'z uzunligi hisobga olinmasa). j ni i - longest dan boshlaymiz: eng uzun so'zdan uzun bo'lak baribir menyuda yo'q. Murakkablik: n ta i × L ta j (L — eng uzun so'z) × slice narxi O(L) = O(n · L²). break — bitta bo'linish topilsa yetarli.

Mantichoy menyuda alohida so'z sifatida ham bor (set taom). oshmantichoy ikki xil bo'linadi: osh manti choy va osh mantichoy — DP "bo'linadimi?" ga javob beradi, bo'linishlar sonini emas. Sonini topish — zinapoya kabi qo'shish bilan. Masala LeetCode'da 139 "Word Break" nomi bilan bor.

Naqsh: "satrni bo'laklarga bo'lish" — dp[i] matn prefiksi uchun, formula oxirgi bo'lak boshi j bo'yicha.

7. Naqshlar jadvali

Xotira: birinchi ikkitasi O(1) ga tushadi, qolganlari — O(n) yoki O(A).

8. Chegaraviy holatlar

• Bo'sh kirish. Aksiya kunlari [] — 0; LIS [] — 0 (Math.max(0, ...dp) dagi 0 shuning uchun); bo'sh matn — true.
• Bitta element. Aksiya — o'sha kun; LIS — 1.
• Imkonsiz summa. Kuponlar [5, 10] bilan 3 ming — Infinity qoladi, funksiya −1 qaytaradi. 0 bilan boshlasangiz, "0 ta kupon" degan noto'g'ri javob chiqadi.
• Takroriy sonlar LIS'da. "Qat'iy o'suvchi" (<) va "kamaymaydigan" (<=) — boshqa masalalar. [5, 5, 5] uchun birinchisida 1, ikkinchisida 3.
• Manfiy tushum. Aksiya kunida tushum manfiy bo'lsa (zarar), formula o'zi uni tashlab ketadi — max uni olmaydi.
• Katta summa, kichik kuponlar. A = 10⁹ bo'lsa, O(A) jadval sig'maydi — bunday shartda boshqa usul kerak (masalan, matematik formula yoki BFS).

9. Ko'p uchraydigan xatolar

9.1 "Imkonsiz" ni 0 bilan to'ldirish

dp = new Array(A + 1).fill(0) bilan eng kam kuponni qidirish — min doim 0 ni tanlaydi, javob noto'g'ri. Tuzatish: eng kichigi qidirilsa — Infinity, eng kattasi — -Infinity.

9.2 Kombinatsiya va tartibni adashtirish

Sikllar tartibini almashtirsangiz, 4 o'rniga 9 chiqadi — xato xabari yo'q. Tuzatish: shartni o'qing va kodda izoh qoldiring: // tartib muhim emas — kuponlar tashqarida.

9.3 LIS javobini dp[n - 1] dan olish

Darsdagi misolda dp[7] = 3, javob esa 4. Tuzatish: "i da tugaydigan" holatda javob — barcha dp ning eng kattasi.

9.4 tails ni javob deb chiqarish

[12, 18, 9, 15, 20, 11, 22, 16] uchun oxirida tails = [9, 11, 16, 22] — bu kunlar tartibida o'suvchi ketma-ketlik emas (9 dan keyin 11 bor, lekin 16 dan keyin 22 yo'q). Tuzatish: tails dan faqat uzunlikni oling. Ketma-ketlikning o'zi kerak bo'lsa — O(n²) versiyada prev indekslarini saqlang (Eng qisqa yo'l darsidagi kabi).

10. Mashqlar

1-mashq (oson): Zinapoyaning narxi

Har pog'onaga chiqish narxi bor (charchoq ballari): cost = [3, 1, 4, 1, 5]. Sardor 0- yoki 1-pog'onadan boshlaydi, 1 yoki 2 pog'ona chiqadi, oxirgi pog'onadan keyingi joyga (tepaga) chiqishi kerak. Har qadam qo'ygan pog'onasi narxini to'laydi. dp[i] — i-pog'onaga qadam qo'yishning eng kam umumiy narxi. Formulani yozing va javobni toping.

2-mashq (o'rta): Qaysi kunlar?

Aksiya masalasida faqat summani emas, kunlarning o'zini ham qaytaring. Ishora: O(1) xotirani qurbon qilib, to'liq dp massivini saqlang. Keyin oxiridan boshlab: dp[i] === dp[i - 1] bo'lsa, i-kun olinmagan; aks holda olingan va i − 2 ga sakraymiz.

function promoDays(gains) {
  const n = gains.length;
  const dp = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    const skip = i >= 1 ? dp[i - 1] : 0;
    const take = (i >= 2 ? dp[i - 2] : 0) + gains[i];
    dp[i] = Math.max(skip, take);
  }
  const days = [];
  for (let i = n - 1; i >= 0; ) {
    if (i >= 1 && dp[i] === dp[i - 1]) {
      i -= 1; // bu kun olinmagan
    } else {
      days.push(i + 1); // kunlar 1 dan sanaladi
      i -= 2;
    }
  }
  return { total: n ? dp[n - 1] : 0, days: days.reverse() };
}
const plan = promoDays([6, 9, 7, 3, 8, 4]);
console.log(plan); // { total: 21, days: [ 1, 3, 5 ] }

3-mashq (qiyin): Kuponlar va LIS — stress test

kurs/mashqlar/14/52-dp-1d/dp1.test.mjs faylida fewestCoupons (tabulation) va LIS ning ikki versiyasini yozing. Testlar (node:test):

1. 0 so'm — 0 ta kupon.
2. [1, 3, 4] bilan 6 — 2 ta (ochko'z usul yutqazadigan holat).
3. Imkonsiz summa va bo'sh kuponlar ro'yxati — −1.
4. Stress: 100 ta tasodifiy kupon jufti va summa — brute force bilan bir xil.
5. Stress: 200 ta tasodifiy massiv — LIS O(n log n) = O(n²).

// kurs/mashqlar/14/52-dp-1d/dp1.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function fewestCoupons(coupons, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coupons) {
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// brute force — faqat kichik summalar uchun
function fewestSlow(coupons, amount) {
  if (amount === 0) return 0;
  let best = Infinity;
  for (const c of coupons) {
    if (c > amount) continue;
    const rest = fewestSlow(coupons, amount - c);
    if (rest !== -1) best = Math.min(best, rest + 1);
  }
  return best === Infinity ? -1 : best;
}

function lisSlow(nums) {
  const dp = nums.map(() => 1);
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return Math.max(0, ...dp);
}

function lisFast(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x;
  }
  return tails.length;
}

function seeded(seed) { // 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("0 so'm — 0 ta kupon", () => {
  assert.equal(fewestCoupons([1, 3, 4], 0), 0);
});

test("ochko'z usul yutqazadigan holat: 6 = 3 + 3", () => {
  assert.equal(fewestCoupons([1, 3, 4], 6), 2);
});

test("imkonsiz summa — -1", () => {
  assert.equal(fewestCoupons([5, 10], 3), -1);
  assert.equal(fewestCoupons([], 7), -1);
});

test("stress: kuponlar brute force bilan bir xil", () => {
  const random = seeded(53);
  for (let round = 0; round < 100; round++) {
    const small = 1 + Math.floor(random() * 6);
    const big = 2 + Math.floor(random() * 9);
    const coupons = [small, big];
    const amount = Math.floor(random() * 25);
    const fast = fewestCoupons(coupons, amount);
    const slow = fewestSlow(coupons, amount);
    assert.equal(fast, slow, `${coupons} ${amount}`);
  }
});

test("stress: LIS O(n log n) = O(n²)", () => {
  const random = seeded(14);
  for (let round = 0; round < 200; round++) {
    const n = Math.floor(random() * 30);
    const nums = [];
    for (let i = 0; i < n; i++) nums.push(Math.floor(random() * 20));
    assert.equal(lisFast(nums), lisSlow(nums));
  }
});

✔ 0 so'm — 0 ta kupon (0.7519ms)
✔ ochko'z usul yutqazadigan holat: 6 = 3 + 3 (0.1462ms)
✔ imkonsiz summa — -1 (0.1072ms)
✔ stress: kuponlar brute force bilan bir xil (3.1809ms)
✔ stress: LIS O(n log n) = O(n²) (1.5393ms)
ℹ tests 5
ℹ suites 0
ℹ pass 5
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 98.4267

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga darsning beshta masalasini qo'shing; LIS uchun ikkala versiyani.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Zinapoya (usullar) | dp, ikki o'zgaruvchi | O(n) | O(1) |
| Aksiya kunlari | ol / o'tkazib yubor | O(n) | O(1) |
| Eng kam kupon | dp summa bo'yicha | O(A · k) | O(A) |
| Kupon usullari | sikllar tartibi | O(A · k) | O(A) |
| LIS | dp, i da tugaydigan | O(n²) | O(n) |
| LIS | tails + binar qidiruv | O(n log n) | O(n) |
| So'zlarga bo'lish | prefiks dp + Set | O(n · L²) | O(n) |

git add 14/MURAKKABLIK.md 14/52-dp-1d
git commit -m "14/52: 1D DP — besh masala, jadval va stress testlar"

11. Real ishda

• Matnni bo'lish. Xitoy va yapon tillarida so'zlar orasida bo'sh joy yo'q — qidiruv tizimlari va klaviaturalar matnni so'zlarga DP bilan bo'ladi. Hashtag'larni o'qish (#bahoroshxonasi → "bahor oshxonasi") ham shunday.
• To'lov va qaytim. Kassa va bankomatlar qaytimni berishda, kupon va keshbek tizimlari esa chegirmani hisoblashda shu masalalarga duch keladi. Kupyuralar tizimi "ochko'z usulga mos" qilib loyihalanadi — lekin sovg'a kuponlari kabi tizimlarda bu kafolat yo'q.
• Moliya va tahlil. "Eng uzun o'sish davri", "eng foydali savdo kunlari" — LIS va "ol yoki o'tkazib yubor" naqshlarining tahlil hisobotlaridagi ko'rinishi.
• Versiyalar va diff. Ikki fayl orasidagi umumiy qatorlarni topish LIS ga yaqin g'oyalardan foydalanadi (patience diff algoritmi).
• Intervyu. House Robber, Coin Change, LIS, Word Break, Climbing Stairs — "Blind 75" va "NeetCode 150" ro'yxatlaridagi 1D DP bo'limining yadrosi (LeetCode uslubidagi muntazam mashq).

Xulosa

• 1D DP'da holat — bitta son: indeks yoki summa. Har masalada besh savol: holat, formula, asos, tartib, javob qayerda.
• "Nechta usul" — guruhlarni qo'shish; "eng yaxshi" — max/min; "mumkinmi" — true/false va ||.
• Kuponlarda imkonsiz holat — Infinity; to'plamlar uchun kuponlar tashqi siklda, tartiblar uchun — summalar.
• "i da tugaydigan" holatda (LIS) javob — butun dp ning eng kattasi. LIS binar qidiruv bilan O(n log n): o'lchovda n ×2 → ≈ ×2,1, O(n²) versiyada ≈ ×4,1.
• Ochko'z tanlov aksiya kunlarida (17 < 21) va kuponlarda (3 > 2) yutqazdi — DP hamma variantni aqlli ko'radi.

Keyingi dars: 2D DP masalalari — ikki o'lchamli jadval: panjaradagi yo'llar, ikki matnning umumiy qismi (LCS), tahrir masofasi va 0/1 xaltacha masalasi.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 14-bob (dinamik dasturlash), 14-4 va 14-5 masalalar.
• Steven S. Skiena, "The Algorithm Design Manual", 3-nashr, Springer, 2020 — 10.3 (LIS), 10.5 (bo'lish masalalari).
• LeetCode 198, 322, 518, 300, 139 — leetcode.com (masala g'oyalari; darsdagi shartlar — o'zimizniki).