Tarkibga o'tish

Dinamik dasturlash

Fibonacci sonlarini hisoblash uchun rekursiv funksiya yozsangiz, fib(5) ni hisoblash uchun fib(4) va fib(3) chaqiriladi. fib(4) esa fib(3) va fib(2) chaqiradi. Natijada fib(3) bir necha marta mustaqil hisoblanadi. Kattaroq sonlar uchun bu takroriy hisoblash eksponensial o'sadi: fib(50) uchun milliardlab operatsiya.

Savol oddiy: fib(3) birinchi hisoblanganda natijasini eslab qolsak, keyin uni boshqa hisoblashga hojat yo'q emas edimi?

Dinamik dasturlash (dynamic programming, DP) aynan shu — bir marta hisoblangan pastki masalalar natijasini saqlab, takroriy hisoblashning oldini olish. Bu texnika bir ko'rinishda rekursiya bilan xotira, boshqa ko'rinishda iteratsiya bilan jadval.

Ikki asosiy xossa

DP faqat quyidagi ikki xossa mavjud bo'lganda qo'llaniladi:

1. Optimal pastki tuzilma (optimal substructure): Masalaning optimal yechimi kichikroq pastki masalalarning optimal yechimlari orqali quriladi.

Misol: A dan C gacha eng qisqa yo'l A → B → C. A → B va B → C bo'laklari ham o'z yo'nalishlarida eng qisqa bo'lishi kerak. Aks holda, ularni yaxshiroq pastki yo'llar bilan almashtirib, umumiy yo'lni yaxshilash mumkin edi.

2. Takrorlanuvchi pastki masalalar (overlapping subproblems): Bir xil kichik masala bir necha marta uchraydi.

Misol: Fibonacci rekursiyasida fib(3) bir necha bor chaqiriladi. Har safar mustaqil hisoblash — isrof. Bir marta hisoblash va eslab qolish — DP.

Agar pastki masalalar takrorlanmasa (masalan, merge sort), DP foyda bermaydi — bu holat "bo'lib-tashla" (divide and conquer) dir.

Eslab qolish usullari

DP natijalarni ikki xil tarzda saqlaydi:

Yuqoridan pastga: memoizatsiya (top-down)

Rekursiv funksiya yoziladi, lekin har hisoblangan natija keshda saqlanadi. Keyingi marta bir xil argument bilan chaqirilganda keshdan olinadi.

memo = bo'sh map

FUNCTION FIB(n)
    IF n ≤ 1
        RETURN n
    IF n memo ichida bor
        RETURN memo[n]
    result   = FIB(n - 1) + FIB(n - 2)
    memo[n]  = result
    RETURN result

Afzalligi: faqat kerakli pastki masalalar hisoblanadi. Oddiy rekursiyaga oz o'zgartirish. Kamchiligi: rekursiya call stack xotira sarflaydi; juda chuqur rekursiyada stack overflow mumkin.

Pastdan yuqoriga: tabulatsiya (bottom-up)

Kichik pastki masalalardan boshlangich, kattalariga qarab jadval to'ldiriladi. Rekursiya yo'q.

FUNCTION FIB(n)
    IF n ≤ 1
        RETURN n
    dp    = n + 1 ta 0 qiymatdan iborat array
    dp[0] = 0
    dp[1] = 1
    FOR i = 2 DAN n GACHA
        dp[i] = dp[i - 1] + dp[i - 2]
    RETURN dp[n]

Afzalligi: call stack yo'q, xotira nazorat qilinadi. Ko'pincha memoizatsiyadan tezroq (cache-friendly). Kamchiligi: barcha pastki masalalar hisoblanadi (ba'zan faqat bir qismiga ehtiyoj bor).

Xotirani optimallashtirish

Ko'p DP masalalarida hamma natijalarni saqlamasdan, faqat "hozirgi qadam uchun keraklilarini" saqlash mumkin. Fibonacci uchun:

FUNCTION FIB(n)
    IF n ≤ 1
        RETURN n
    prev2 = 0
    prev1 = 1
    FOR i = 2 DAN n GACHA
        current = prev1 + prev2
        prev2   = prev1
        prev1   = current
    RETURN prev1

O(n) xotira o'rniga O(1). Bu optimallashtirish "faqat oxirgi k qiymat kerak" degan holatlarda ishlaydi.

DP masalasini aniqlash

Masalani ko'rib quyidagi savollarga javob beriladi:

1. "Optimal" so'zi bormi? Minimal, maksimal, eng qisqa, eng ko'p — bular optimallik belgisi.

2. Kichikroq masalaga qisqartirilsin? f(n) ni f(n-1) yoki f(n-2) orqali ifodalash mumkinmi?

3. Takroriy hisoblash bormi? Agar rekursiv yechim yozilganda bir xil argument bilan bir necha marta chaqirilsa — DP mos.

4. Greedy bilan yechib bo'ladimi? Greedy ishlamasa, DP ko'rib chiqiladi.

DP yechim qadamlari

1. Pastki masalani aniqlang. dp[i] yoki dp[i][j] neni anglatadi? Bu eng muhim qadam — to'g'ri ta'rif berilgach, qolgan qismlar keladi.

2. Rekurrentlik munosabatini (recurrence) tuzing. dp[i] qanday oldingi qiymatlardan hisoblanadi?

3. Boshlanish holatlarini (base case) belgilang. dp[0], dp[1] qanday?

4. Hisoblash tartibini aniqlang. Qaysi qiymatlar avval kerak?

5. Javobni chiqaring. dp[n], dp[n][m] yoki boshqa qiymat.

Klassik DP turlari

1D DP: ketma-ket elementlar

Masala bitta o'lchamdagi massiv yoki son bilan. dp[i] — i-gacha bo'lgan optimal qiymat.

Misol: zinapoya (dp[i] = i-zinapoyaga necha yo'l):

dp[i] = dp[i-1] + dp[i-2]

Misol: uy o'g'risi (dp[i] = i-uy kirganda maksimal o'g'irlik):

dp[i] = MAX(dp[i-1], dp[i-2] + nums[i])

2D DP: ikki o'lcham

Masala ikki ketma-ketlik yoki ikkita o'zgaruvchi bilan. dp[i][j] — i va j gacha bo'lgan holat.

Misol: LCS (eng uzun umumiy ketma-ketlik):

dp[i][j] = dp[i-1][j-1] + 1           (s1[i] = s2[j])
dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]) (boshqa holat)

Misol: edit distance (bir stringni boshqasiga aylantirish minimal qadami):

dp[i][j] = dp[i-1][j-1]                             (s1[i] = s2[j])
dp[i][j] = 1 + MIN(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (boshqa)

Knapsack DP

Resurs chegarasi bilan maksimal qiymat. Ikki turi bor:

0/1 knapsack: har predmet faqat bir marta olinadi.

dp[i][w] = MAX(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

Unbounded knapsack: har predmet cheksiz marta olinishi mumkin (coin change).

dp[w] = MIN(dp[w], dp[w - coin] + 1)

Interval DP

Oraliq [l, r] ning optimal qiymatini uning kichik oraliqlaridan qurish.

Misol: matritsa zanjiri ko'paytmasi (opsional kesish nuqtasini tanlash):

dp[l][r] = MIN over all k in (l, r) of:
           dp[l][k] + dp[k][r] + cost(l, k, r)

DP va boshqa yondashuvlar

Xususiyat Greedy Backtracking DP
Qaror qabul qilish Bir qadam, qaytmasdan Barcha variantlar, bekor qilish Pastki masalalar natijasiga tayanib
Takroriy hisoblash Yo'q Ko'p Bir marta, keyin xotiradan
Optimal kafolat Faqat ma'lum masalalar Barcha yechimlarni topadi Optimal substructure bo'lsa — kafolat
Murakkablik Odatda O(n log n) Eksponensial Polinom (ko'pincha O(n²), O(nW))

Keng tarqalgan DP masalalar

  • Fibonacci: dp[i] = dp[i-1] + dp[i-2]
  • Zinapoya: dp[i] = dp[i-1] + dp[i-2]
  • Uy o'g'risi: dp[i] = MAX(dp[i-1], dp[i-2] + nums[i])
  • Coin change: dp[amount] = MIN(dp[amount - coin] + 1)
  • Longest increasing subsequence: dp[i] = MAX(dp[j] + 1) for j < i if nums[j] < nums[i]
  • Edit distance: ikki o'lchamli DP
  • Unique paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]
  • Partition equal subset sum: subset sum — knapsack varianti

Keng tarqalgan xatolar

Pastki masala ta'rifining noto'g'riligi

dp[i] neni anglatishini aniq belgilamaslik — eng keng tarqalgan xato. "Maksimal qiymat" deyilsa, i-gacha boshlang'ichdan maksimalmi yoki i-elementdan tugaydigan qismning maksimalimi — bu farq javobni o'zgartiradi.

Base case yo'q yoki noto'g'ri

dp[0] va dp[1] to'g'ri belgilanmasa, butun jadval noto'g'ri to'ldiriladi. Array chegarasidan tashqarida index xatosi ham shu sababdan paydo bo'ladi.

Hisoblash tartibini buzish

dp[i] hisoblashda dp[i+1] kerak bo'lsa — tartibda xato. dp[i] hisoblash uchun zarur barcha qiymatlar avvalroq hisoblanib bo'lishi kerak.

2D DPda xotira optimallashtirish xatosi

Qatorsaqlovchi optimallashtirishda faqat oldingi qatorga murojaat qilinishi kerak. Agar dp[i][j] hisoblashda dp[i-2][j] ham kerak bo'lsa, bitta qatorga qisqartirish xato beradi.

Memoizatsiyada immutable argumentlar

Memoizatsiya uchun argument kesh kaliti bo'ladi. Agar argument mutable (masalan, array) va o'zgarib boruvchi bo'lsa, kesh noto'g'ri qaytarib berishi mumkin. Immutable qiymatlar (son, tuple) yoki nusxa ishlatish kerak.

Qachon DP ishlatish kerak?

  • Optimal (minimal/maksimal) qiymat kerak bo'lganda
  • Bir xil pastki masalalar takrorlanayotganda
  • Greedy noto'g'ri natija berayotganda
  • Backtracking juda sekin bo'lganda, lekin barcha yechimlar emas — faqat optimal kerak bo'lganda

Qachon DP ishlatmaslik kerak?

  • Pastki masalalar takrorlanmasa — divide and conquer yetarli
  • Optimal substructure xossasi yo'q bo'lsa
  • Kirish katta va holat o'lchami (state space) juda katta bo'lsa — xotira yetmaydi
  • Greedy bilan provably optimal natija olinsa — DP ortiqcha

Xulosa

Dinamik dasturlash — takroriy hisoblashni bir marta hisoblash va saqlash orqali hal qilish. Ikki xossa: optimal pastki tuzilma (kichik masalalardan katta yechim) va takrorlanuvchi pastki masalalar.

Memoizatsiya — rekursiya bilan kesh. Tabulatsiya — jadval bilan iteratsiya. Ikkisi ekvivalent, lekin tabulatsiya ko'pincha tezroq va xotira optimallashtirish osonroq.

Eng muhim qadam — pastki masalani to'g'ri aniqlash: dp[i] nima? Bu savolga aniq javob bilan rekurrentlik munosabati va base case natural ravishda keladi.