Tangalar (Coin Change)

Turli nominallik tangalar berilgan. Ma'lum miqdorni (amount) to'lash uchun minimal tangalar sonini toping. Agar to'lab bo'lmasa — -1 qaytaring.

Har nominallik tangadan cheksiz miqdorda ishlatish mumkin.

Kirish: coins = [1, 5, 10, 25],  amount = 41
Chiqish: 4
Izoh: 25 + 10 + 5 + 1 = 41, 4 ta tanga

Kirish: coins = [1, 5, 6, 9],  amount = 11
Chiqish: 2
Izoh: 5 + 6 = 11, 2 ta tanga (greedy 9+1+1 = 3 ta beradi — noto'g'ri)

Kirish: coins = [2],  amount = 3
Chiqish: -1
Izoh: 3 ni 2-liklardan to'lab bo'lmaydi

Kirish: coins = [1],  amount = 0
Chiqish: 0

Nima uchun greedy ishlamaydi?

coins = [1, 5, 6, 9], amount = 11:

Greedy (katta nominaldan): 9 + 1 + 1 = 3 tanga. Optimal: 5 + 6 = 2 tanga.

Greedy 9ni tanlaydi chunki eng katta. Lekin bu keyingi tanlovlarni cheklaydi. DP barcha variantlarni ko'rib chiqib optimalini topadi.

Asosiy g'oya: pastki masala

dp[i] — i miqdorni to'lash uchun minimal tangalar soni.

Har dp[i] uchun barcha tangalarni sinab ko'ramiz: i - coin ni to'lash mumkin bo'lsa, u holatdan +1 tanga bilan i to'lanadi:

dp[i] = MIN over all coin in coins of:
         dp[i - coin] + 1   (agar i - coin >= 0)

Base case: dp[0] = 0 — 0 miqdorni to'lash uchun 0 tanga.

Boshlanish holati: barcha dp[1..amount] = INFINITY — hali hisoblanmagan, to'lab bo'lmaydi deb olinadi.

Pseudocode

FUNCTION COIN_CHANGE(coins, amount)
    dp    = amount + 1 ta (amount + 1) qiymatdan iborat array
    dp[0] = 0

    FOR i = 1 DAN amount GACHA
        FOR har bir coin coins ichida
            IF coin ≤ i VA dp[i - coin] + 1 < dp[i]
                dp[i] = dp[i - coin] + 1

    IF dp[amount] > amount
        RETURN -1
    RETURN dp[amount]

Nima uchun INFINITY o'rniga amount + 1 ishlatiladi? amount + 1 bu vaziyatda "to'lab bo'lmaydi" belgisi. Chunki amount ni to'lash uchun ko'pi bilan amount ta 1-lik tanga kerak — haqiqiy minimal soni bu chegaradan oshmaydi. dp[amount] > amount bo'lsa — to'lab bo'lmadi.

Bosqichma-bosqich dry run

coins = [1, 2, 5], amount = 11:

dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
                                                 // amount+1 = 12

i=1:
  coin=1: dp[1-1]+1 = dp[0]+1 = 1 < 12 → dp[1]=1
  coin=2: 2>1, o'tkaziladi
  coin=5: 5>1, o'tkaziladi

i=2:
  coin=1: dp[2-1]+1 = dp[1]+1 = 2 → dp[2]=2
  coin=2: dp[2-2]+1 = dp[0]+1 = 1 < 2 → dp[2]=1
  coin=5: 5>2, o'tkaziladi

i=3:
  coin=1: dp[2]+1 = 2
  coin=2: dp[1]+1 = 2
  → dp[3] = 2

i=4:
  coin=1: dp[3]+1 = 3
  coin=2: dp[2]+1 = 2
  → dp[4] = 2

i=5:
  coin=1: dp[4]+1 = 3
  coin=2: dp[3]+1 = 3
  coin=5: dp[0]+1 = 1
  → dp[5] = 1

i=6:
  coin=1: dp[5]+1 = 2
  coin=2: dp[4]+1 = 3
  coin=5: dp[1]+1 = 2
  → dp[6] = 2

i=7: coin=2: dp[5]+1=2, coin=5: dp[2]+1=2 → dp[7]=2
i=8: coin=1: dp[7]+1=3, coin=2: dp[6]+1=3, coin=5: dp[3]+1=3 → dp[8]=3
i=9: coin=2: dp[7]+1=3, coin=5: dp[4]+1=3 → dp[9]=3
i=10: coin=5: dp[5]+1=2 → dp[10]=2
i=11: coin=1: dp[10]+1=3, coin=2: dp[9]+1=4, coin=5: dp[6]+1=3 → dp[11]=3

dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
RETURN dp[11] = 3

11 = 5 + 5 + 1 — 3 ta tanga.

Vaqt va xotira murakkabligi

Xususiyat	Qiymat	Izoh
Vaqt	`O(amount × n)`	Har `i` uchun barcha `n` tanga ko'riladi
Xotira	`O(amount)`	`dp` array

n — tangalar soni.

Edge case'lar

amount = 0: dp[0] = 0, 0 tanga.

To'lab bo'lmaydi. coins = [2], amount = 3 — dp[3] hech yangilanmaydi, 4 (amount+1) bo'lib qoladi → -1.

Bitta tanga, amount uning karrali. coins = [3], amount = 9 → dp[9] = 3.

Katta amount. Xotira O(amount) — juda katta amount uchun muammo bo'lishi mumkin.

Bir xil nominallar. coins = [1, 1, 1] — takroriy bir xil tangalar. Natijaga ta'sir qilmaydi, lekin DP iteratsiyasi uch marta bir xil tanini tekshiradi. Oldindan noyob tangalar olinsa optimalroq.

Note

Bu unbounded knapsack (cheksiz qayta ishlatiladigan predmetlar) DP ning klassik ko'rinishi. Har tanga cheksiz ishlatilishi mumkin shuning uchun dp[i-coin] da oldingi holatga qaytish kerak — bir o'lchamli DP bu holat uchun to'g'ri.

0/1 knapsack bilan farqi

0/1 knapsack (har predmet bir marta):

FOR har bir coin coins ichida
    FOR i = amount DAN coin GACHA (teskari!)
        dp[i] = MIN(dp[i], dp[i - coin] + 1)

Teskari iteratsiya har tangani faqat bir marta ishlatish kafolatini beradi.

Coin change (cheksiz):

FOR i = 0 DAN amount GACHA
    FOR har bir coin coins ichida
        dp[i] = MIN(dp[i], dp[i - coin] + 1)

Oldinga iteratsiya — bitta tanga bir necha marta ishlatilishi mumkin.

Kengaytirilgan variant: kombinatsiyalar soni

Minimal tangalar soni emas, necha xil kombinatsiya bilan to'lash mumkinligi:

FUNCTION CHANGE(amount, coins)
    dp    = amount + 1 ta 0 qiymatdan iborat array
    dp[0] = 1   // 0 to'lashning 1 ta yo'li: hech narsa olmang

    FOR har bir coin coins ichida
        FOR i = coin DAN amount GACHA
            dp[i] = dp[i] + dp[i - coin]

    RETURN dp[amount]

Tashqi tsikl tanga, ichki tsikl miqdor — bu tartib kombinatsiyalarni sanashda muhim (tartib farq qilmaydi — kombinatsiyalar, tartibi farq qilsa — permutatsiyalar).

Xulosa

Coin change — unbounded knapsack DP. dp[i] = i miqdorni to'lash uchun minimal tangalar. Rekurrentlik: dp[i] = MIN(dp[i - coin] + 1) barcha tangalar uchun.

Greedy nominallar bir-birining karrasi bo'lmagan holatlarda noto'g'ri natija beradi. DP barcha variantlarni ko'rib optimal tanlovni kafolatlaydi. Vaqt: O(amount × n), xotira: O(amount).