3.12-bob: Dinamik dasturlash (DP) asoslari

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 12-mavzu

1. Kirish va motivatsiya

Rekursiyada 3.11-bob fibonacci uchun O(2ⁿ) sekinlikni ko'rdik — bir xil qiymat qayta-qayta hisoblanardi. Dinamik dasturlash (DP) aynan shu isrofni hal qiladi: hisoblangan natijalarni saqlab, qayta hisoblamaslik. Bu — eksponensial (O(2ⁿ)) yechimni ko'pincha chiziqli (O(n)) ga tushiradi.

DP — algoritmikaning eng "qo'rqinchli" mavzusi deb hisoblanadi, lekin asosi oddiy: takrorlanuvchi kichik muammolarni bir marta yechib, natijani eslab qolish (rekursiya — 3.11 + Hash Table — 3.5). Bu — intervyularning eng qiyin, eng ko'p baholanadigan qismi.

O'xshatish: imtihonga tayyorlanayotganingizni tasavvur qiling. Har masalani yechganingizda javobni daftarga yozib qo'yasiz. Keyingi safar o'sha masala chiqsa — qaytadan yechmaysiz, daftardan o'qiysiz. DP — aynan shu: bir marta hisoblang, saqlang, qayta ishlating. "Bir xil ishni ikki marta qilmang."

Nega muhim?

• Eksponensial chiziqli/polinomial tezlik (katta tejash).
• Optimallashtirish masalalari: eng qisqa yo'l, eng katta foyda, eng kam qadam.
• Real: matn farqi (diff/git — 4), DNA mosligi, resurs taqsimlash, marshrutlash.
• Intervyularning eng qiyin, eng baho beradigan qismi.

2. Nazariya — chuqur tushuntirish

2.1. DP qachon qo'llanadi: ikki shart

DP faqat ikki xususiyatga ega masalalarga qo'llanadi:

1. Overlapping subproblems (takrorlanuvchi kichik muammolar) — bir xil kichik muammo qayta-qayta yechiladi (fibonacci: fib(3) ko'p marta).
2. Optimal substructure (optimal kichik tuzilma) — katta muammoning optimal yechimi kichiklarining optimal yechimlaridan quriladi.

Agar kichik muammolar takrorlanmasa — DP foydasiz (oddiy rekursiya/divide-conquer). Bu ikki shartni tanish — DP'ni qo'llashning kaliti.

2.2. Fibonacci muammosi — DP motivatsiyasi

  Naive rekursiya fib(5):
              fib(5)
            /        \
        fib(4)        fib(3)
        /    \        /    \
    fib(3)  fib(2) fib(2) fib(1)    fib(3), fib(2) QAYTA-QAYTA!
    ...
  O(2ⁿ) — bir xil qiymat eksponensial marta hisoblanadi

fib(50) naive — soatlab! Chunki fib(3) milliardlab marta hisoblanadi. DP buni hal qiladi.

2.3. DP usuli 1: Memoization (top-down)

Memoization — rekursiya 3.11-bob + cache 3.5-bob: hisoblangan natijani saqlab, qayta so'ralganda cache'dan berish:

function fib(n, memo = {}) {
  if (n <= 1) return n;              // base case (3.11)
  if (n in memo) return memo[n];    // CACHE'da bormi? 3.5-bob — qayta hisoblamaydi
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);   // hisobla va SAQLA
  return memo[n];
}
fib(50);   // darrov! O(n) — har qiymat BIR MARTA hisoblanadi

Top-down (yuqoridan-pastga): rekursiyadan boshlanadi, kerakli kichik muammolarni hisoblab, cache'laydi. Tabiiy (rekursiyani memo bilan "bezatish"). O(n) vaqt, O(n) xotira.

2.4. DP usuli 2: Tabulation (bottom-up)

Tabulation — kichik muammolardan boshlab, jadval (massiv) to'ldirib, kattaga boriladi (rekursiyasiz):

function fib(n) {
  if (n <= 1) return n;
  const dp = [0, 1];                 // jadval: dp[i] = fib(i)
  for (let i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];   // kichikdan kattaga (tsikl — 2.2)
  return dp[n];
}
// O(n) vaqt, O(n) xotira; rekursiyasiz (stack overflow yo'q — 3.11)

Bottom-up (pastdan-yuqoriga): eng kichik holatdan boshlab, jadvalni ketma-ket to'ldiradi. Stack overflow yo'q; ko'pincha xotira optimallashtirilishi mumkin.

2.5. Xotira optimallashtirish

Fibonacci'da faqat oxirgi ikki qiymat kerak — butun massiv shart emas (O(n) O(1) xotira):

function fib(n) {
  if (n <= 1) return n;
  let oldingi = 0, joriy = 1;
  for (let i = 2; i <= n; i++) {
    [oldingi, joriy] = [joriy, oldingi + joriy];   // faqat 2 qiymat (2.8: swap)
  }
  return joriy;
}
// O(n) vaqt, O(1) xotira — eng optimal (3.1: vaqt vs xotira)

2.6. Memoization vs Tabulation

Qaysi? Boshda memoization osonroq (rekursiyani memo bilan o'rash). Keyin tabulation'ga o'tib, xotirani optimallashtirish mumkin. Ikkalasi ham O(n) vaqt (fibonacci uchun).

2.7. DP'ga yondashuv (5 qadam)

Murakkab DP masalasini yechish bosqichlari (0.6: muammoga yondashuv):

  1. STATE (holat) aniqla — dp[i] nimani anglatadi? (masalan "i-qadamgacha min narx")
  2. RECURRENCE (rekurrent munosabat) — dp[i] kichiklaridan qanday hisoblanadi?
  3. BASE CASE — eng kichik holat(lar) qiymati
  4. TARTIB — qaysi tartibda hisoblash (bottom-up)
  5. JAVOB — qaysi dp qiymati natija

2.8. Klassik DP masalalari

• Fibonacci / pog'onalar (n-pog'onaga necha usul).
• Coin change — minimal tangalar bilan summa yig'ish.
• Knapsack (ryukzak) — vazn cheklovida max qiymat.
• Longest Common Subsequence (LCS) — ikki matn umumiy ketma-ketligi (diff — 4).
• Edit distance — bir matnni boshqasiga aylantirish min amallar.
• Longest Increasing Subsequence (LIS) — eng uzun o'suvchi qism.
• Grid path — to'rda yo'llar soni / min narx.

3. Sintaksis — tez ma'lumotnoma

DP SHARTI:    overlapping subproblems + optimal substructure 2.1-bob
MEMOIZATION:  rekursiya + memo cache (top-down) — if (n in memo) return ...
TABULATION:   dp[] jadval + tsikl (bottom-up) — dp[i] = f(dp[i-1]...)
XOTIRA OPT:   faqat kerakli oldingi qiymatlar (O(n)  O(1))
YONDASHUV:    state  recurrence  base  tartib  javob (2.7)

4. Batafsil kod namunalari

Misol 1 — Pog'onalar (climbing stairs — 2.3, 2.4)

// n-pog'onaga 1 yoki 2 qadamlab chiqishning necha usuli? (= fibonacci!)
// Memoization (top-down — 2.3)
function pogonalar(n, memo = {}) {
  if (n <= 2) return n;                 // base: 11, 22
  if (n in memo) return memo[n];
  memo[n] = pogonalar(n - 1, memo) + pogonalar(n - 2, memo);   // oxirgi qadam 1 yoki 2
  return memo[n];
}

// Tabulation + xotira optim (bottom-up — 2.4, 2.5)
function pogonalarTab(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
pogonalar(5);   // 8 usul

Misol 2 — Coin change (min tangalar — 2.8)

// summa'ni eng kam tanga bilan yig'ish (tangalar cheksiz)
function coinChange(tangalar, summa) {
  const dp = Array(summa + 1).fill(Infinity);   // dp[i] = i ni yig'ish min tanga
  dp[0] = 0;                                      // base: 0 summa  0 tanga (2.7)
  for (let i = 1; i <= summa; i++)
    for (const tanga of tangalar)
      if (tanga <= i) dp[i] = Math.min(dp[i], dp[i - tanga] + 1);  // recurrence
  return dp[summa] === Infinity ? -1 : dp[summa];  // imkonsiz  -1
}
coinChange([1, 5, 10, 25], 30);   // 2 (25 + 5)
// O(summa × tangalar) — eksponensial brute force o'rniga

Misol 3 — Longest Common Subsequence (LCS — 2.8)

// Ikki matnning eng uzun umumiy ketma-ketligi (git diff g'oyasi — 4)
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++)
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1                    // mos  diagonal + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);   // mos emas  max
  return dp[a.length][b.length];
}
lcs("ABCBDAB", "BDCAB");   // 4 ("BCAB")
// 2D DP jadval — O(m × n)

Misol 4 — Naive vs DP tezlik (2.2, 3.1)

// Naive fibonacci — O(2ⁿ) (3.11)
function fibNaive(n) { return n <= 1 ? n : fibNaive(n - 1) + fibNaive(n - 2); }

// DP fibonacci — O(n) (2.5)
function fibDP(n) { let a = 0, b = 1; for (let i = 2; i <= n; i++) [a, b] = [b, a + b]; return b; }

console.time("naive"); fibNaive(35); console.timeEnd("naive");   // ~sekundlar!
console.time("dp"); fibDP(35); console.timeEnd("dp");            // ~0 ms
// fib(50): naive — soatlab; DP — bir lahza (3.1)

5. To'g'ri va noto'g'ri holatlar

1) Takror hisob (memoization'siz)

//  naive rekursiya — O(2ⁿ) (3.11, 2.2)
function fib(n) { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }

//  memoization — O(n) (2.3)
function fib(n, memo = {}) { /* cache bilan */ }

2) DP'ni har joyga qo'llash

 takrorlanuvchi kichik muammo yo'q bo'lsa DP — keraksiz murakkablik (2.1)
 avval 2 shartni tekshir (overlapping + optimal substructure)

3) Base case / chegara xato

//  dp jadvali noto'g'ri boshlangan (dp[0] xato — 2.7)
const dp = Array(n + 1).fill(0);   // coin change'da Infinity kerak edi

//  to'g'ri base/boshlang'ich qiymat (Misol 2: Infinity, dp[0]=0)

4) Xotirani optimallashtirmaslik (kerak bo'lganda)

//  butun massiv (O(n) xotira) — faqat 2 qiymat kerak edi
//  ikki o'zgaruvchi (O(1) — 2.5)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — DP sekin/eksponensial (memo ishlamayapti)

Sababi: cache to'g'ri ishlatilmagan yoki kalit noto'g'ri (2.3, 3.5). Yechimi: if (kalit in memo) return ni hisobdan oldin qo'ying; kalit aniq bo'lsin.

Xato 2 — Noto'g'ri natija (recurrence xato)

Sababi: rekurrent munosabat noto'g'ri 2.7-bob. Yechimi: kichik misolda qo'lda jadval to'ldiring 0.6-bob; state ta'rifini aniqlang.

Xato 3 — RangeError: Maximum call stack (memoization)

Sababi: chuqur rekursiya (katta n — 3.11, 0.1). Yechimi: tabulation (bottom-up — 2.4) — rekursiyasiz.

Xato 4 — 2D DP indeks xatosi

Sababi: dp[i-1][j-1] chegaradan tashqari (off-by-one — 0.6). Yechimi: jadvalni (m+1)×(n+1) qiling; i, j 1 dan boshlang (Misol 3).

Xato 5 — DP qo'llab bo'lmaydigan masalaga urinish

Sababi: masala DP shartlariga mos emas 2.1-bob. Yechimi: boshqa usul (greedy, backtracking — 3.11, graf — 3.7).

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Rekursiya 3.11-bob: memoization — rekursiya + cache.
• Hash Table 3.5-bob: memo cache.
• Big-O 3.1-bob: O(2ⁿ) O(n) — DP ning asosiy yutug'i.
• Saralash/qidiruv (3.9, 3.10): ba'zi DP saralangan ma'lumotda.
• Graf 3.7-bob: ba'zi DP graf ustida (eng qisqa yo'l variantlari).
• Real: git diff (4: LCS), matn taqqoslash, resurs optimallashtirish.
• Masala yechish 3.13-bob: DP — eng qiyin masala sinfi.

8. Eng yaxshi amaliyotlar (best practices)

• DP shartlarini tekshiring (overlapping + optimal substructure) — qo'llashdan oldin 2.1-bob.
• Boshda memoization (rekursiya + cache — oson); keyin tabulation/optim 2.6-bob.
• 5 qadamli yondashuv: state recurrence base tartib javob 2.7-bob.
• Kichik misolda jadvalni qo'lda to'ldiring — recurrence'ni tekshirish (0.6, 6-bo'lim).
• Xotirani optimallashtiring — faqat kerakli oldingi qiymatlar (O(n)O(1) — 2.5).
• Chuqur rekursiyada tabulation — stack overflow'dan saqlaydi 2.4-bob.
• Memo kalitini aniq tuting 3.5-bob — to'g'ri cache.
• DP — eng qiyin; ko'p masala yechib o'rganing 3.13-bob — naqshlarni taning.

9. Amaliy loyiha: "Dinamik Dasturlash Masalalari"

DP'ni amalda mustahkamlash — 3-QISMning so'nggidan oldingi loyihasi.

Maqsad

Memoization va tabulation'ni, DP shartlarini va 5 qadamli yondashuvni o'zlashtirish; eksponensial polinomial tezlikni isbotlash.

Talablar (requirements)

Har masala uchun: memoization (top-down) va tabulation (bottom-up) versiyalari, Big-O, naive bilan tezlik solishtirish:

1. Fibonacci / pog'onalar (Misol 1) + xotira optimallashtirish (O(1) — 2.5).
2. Coin change — min tanga (Misol 2); imkonsiz holatni qaytaring.
3. House robber — qo'shni bo'lmagan uylardan max o'g'irlik (klassik).
4. Longest Increasing Subsequence (LIS) — eng uzun o'suvchi qism.
5. Grid paths — to'rda yuqori-chap'dan past-o'ngga yo'llar soni.
6. Longest Common Subsequence (LCS) — 2D DP (Misol 3).
7. Naive vs DP tezlik: fibonacci'ni naive va DP'da o'lchang — farqni ko'rsating (Misol 4, 3.1).
8. Har masala uchun 5 qadamni (state/recurrence/base/tartib/javob) yozing 2.7-bob.
9. Chegaraviy holatlar: 0, bo'sh, imkonsiz 0.6-bob.

Maslahatlar (hint)

• Memoization: memo object/Map 3.5-bob; if (kalit in memo) return.
• Tabulation: dp massiv, kichikdan kattaga tsikl 2.4-bob.
• 5 qadam: "dp[i] nimani anglatadi?" dan boshlang 2.7-bob.
• 2D DP: (m+1)×(n+1) jadval, indeks 1 dan (Misol 3, 4-xato).
• Kichik misolda jadvalni qo'lda to'ldiring (recurrence tekshirish).
• Xotira optim: faqat oldingi qator/qiymatlar 2.5-bob.

"Tayyor" mezonlari (acceptance criteria)

• Har masala memoization va tabulation'da ishlaydi.
• Fibonacci xotira O(1) versiyasi bor.
• Coin change imkonsiz holatni to'g'ri qaytaradi.
• 2D DP (LCS) to'g'ri (indeks xatosiz).
• Naive vs DP tezlik farqi o'lchangan va ko'rsatilgan.
• Har masala uchun 5 qadam yozilgan.
• Chegaraviy holatlar qulamaydi.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda algoritmikaning eng qiyin mavzusi — Dinamik dasturlashni o'rgandik:

• DP — takrorlanuvchi kichik muammolarni bir marta yechib, saqlash (qayta hisoblamaslik); O(2ⁿ) O(n).
• Shartlar: overlapping subproblems + optimal substructure 2.1-bob.
• Memoization (top-down — rekursiya + cache — 3.5) va tabulation (bottom-up — jadval + tsikl).
• Xotira optimallashtirish — faqat kerakli oldingi qiymatlar (O(n)O(1)).
• 5 qadam: state recurrence base tartib javob.
• Klassik: coin change, knapsack, LCS, edit distance, LIS.

Keyingi bob — 3.13-bob: Masala yechish strategiyalari (LeetCode uslubida). Barcha tuzilma va algoritmlarni (3.1–3.12) bildik; endi ularni birlashtirib, yangi masalaga qanday yondashishni — naqshni tanish, strategiya, optimallashtirishni — o'rganamiz. Bu — 3-QISMning yakuni va intervyuga tayyorlanishning kaliti.

Foydalanilgan rasmiy/ishonchli manbalar

• Universal CS — dynamic programming, memoization, tabulation, optimal substructure
• bigocheatsheet.com — DP murakkabligi (eksponensial polinomial)
• MDN Web Docs — rekursiya 3.11-bob, Map/object cache (3.5)