Coin Change

Sizga turli nominallardan iborat coins massivi va umumiy amount miqdori berilgan.

Shu miqdorni yasash uchun zarur bo'lgan eng kam tangalar sonini qaytaring. Agar hech qanday kombinatsiya bilan o'sha miqdorni yig'ish imkoni bo'lmasa, -1 qaytaring.

Har bir nominal cheksiz miqdorda mavjud deb hisoblashingiz mumkin.

func solve(coins []int, amount int) int {
    // ...
}

Misollar

Input: coins = [1,5,11], amount = 11
Output: 1
Tushuntirish: 11 tanga bilan 11 ni yasash mumkin, bu eng kamosi.

Input: coins = [1,2,5], amount = 11
Output: 3

Input: coins = [2], amount = 3
Output: -1

Maslahatlar

1. Har bir miqdor (0 dan amount gacha) uchun "shu miqdorni yig'ish uchun kerak bo'lgan eng kam tanga soni"ni saqlaydigan dinamik dasturlash jadvalini tuzishni o'ylab ko'ring.
2. dp[0]=0 dan boshlang; har bir i=1..amount uchun barcha tangalarni sinab ko'ring — agar tanga qiymati i dan katta bo'lmasa, dp[i] ni dp[i-tanga]+1 bilan solishtirib eng kichigini saqlang; oxirida dp[amount] hali cheksiz (erishib bo'lmaydigan) qolsa -1 qaytaring.