Coin Change
Kamu mendapatkan sebuah list coins berisi nilai koin yang berbeda dan sebuah target amount. Kamu boleh menggunakan setiap nilai koin sebanyak yang kamu mau. Kembalikan jumlah koin paling sedikit yang nilainya jika dijumlahkan tepat sama dengan amount, atau -1 jika tidak ada kombinasi koin yang bisa mencapai jumlah tersebut. Jumlah 0 membutuhkan 0 koin.
Fungsi
- coinsinteger-array
- berbagai nilai koin, masing-masing dapat digunakan berapa kali pun
- amountinteger
- total yang harus dibayar dengan tepat
- Mengembalikaninteger
- jumlah koin paling sedikit yang dibutuhkan, atau -1 jika jumlah tersebut tidak dapat dibuat
Batasan
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- Semua nilai koin berbeda.
Contoh
- Input
- coins = [2, 5, 10]amount = 27
- Output
- 4
- Penjelasan
- 10 + 10 + 5 + 2 menghasilkan 27 dengan empat koin. Tiga koin tidak cukup: 27 adalah bilangan ganjil, jadi kamu membutuhkan tepat satu koin 5, dan dua koin lainnya hanya berjumlah paling banyak 20, kurang dari 22.
- Input
- coins = [4, 6]amount = 7
- Output
- -1
- Penjelasan
- Kedua nilai koin genap, jadi setiap total yang bisa kamu bentuk adalah genap. 7 ganjil, jadi jawabannya adalah -1.
- Input
- coins = [3, 7]amount = 0
- Output
- 0
- Penjelasan
- Membayar 0 tidak membutuhkan koin sama sekali, jadi jawabannya adalah 0 berapa pun nilai koinnya.
Pertanyaan lanjutan
Bisakah kamu menghitung berapa banyak kombinasi koin berbeda yang jumlahnya mencapai amount, alih-alih mencari jumlah koin paling sedikit?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Selalu mengambil koin terbesar yang muat tidak selalu menghasilkan jumlah koin paling sedikit. Coba terapkan pada koin
[1, 3, 4]dan jumlah6.Misalkan kamu sudah mengetahui jumlah koin paling sedikit untuk setiap nilai yang lebih kecil dari
t. Dari nilai yang lebih kecil mana saja kamu bisa mencapaitdengan satu koin tambahan?Isi tabel
fewest[0..amount]dari0ke atas:fewest[0] = 0, dan setiapfewest[t]bernilai satu lebih banyak daripadafewest[t - c]terbaik di antara koinc <= t. Tandai jumlah yang tidak dapat dicapai siapa pun dengan nilai yang lebih besar daripada jawaban nyata mana pun, sepertiamount + 1, lalu ubah menjadi-1di akhir.
Solusi
Mengambil koin terbesar yang pas tidak berhasil: dengan koin 1, 3, dan 4, jumlah 6 dibayar dengan 4 + 1 + 1, sedangkan 3 + 3 hanya membutuhkan dua koin. Jumlah koin paling sedikit untuk suatu nominal hanya bergantung pada jumlah koin paling sedikit untuk nominal yang lebih kecil, jadi kamu menyelesaikan setiap nominal dari 0 sampai amount satu kali.
Coba setiap kombinasi dengan rekursi
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Jika koin terakhir yang kamu bayarkan bernilai c, koin-koin sebelumnya membayar remaining - c dengan cara semurah mungkin. Jadi, fewest(remaining) adalah satu lebih banyak daripada nilai terbaik fewest(remaining - c) untuk setiap koin yang sesuai. Cara ini mencoba setiap urutan koin yang jumlahnya tidak melebihi nilai yang dituju, jadi solusi terbaik pasti ditemukan.
Program ini menghitung jumlah yang sama berulang kali. Dengan koin 2, 5, dan 10, jumlah 27 mencapai 15 setelah membayar 10 + 2, 2 + 10, 5 + 5 + 2, dan urutan lainnya, lalu menghitung 15 dari awal setiap kali. Jumlah pemanggilan bertambah secara eksponensial seiring bertambahnya jumlah.
Algoritma
- Tulis fungsi pembantu
fewest(remaining)yang mengembalikan jumlah koin paling sedikit untukremaining, atau -1 jika tidak ada yang berhasil. - Jika
remainingadalah 0, kembalikan 0. - Untuk setiap koin yang nilainya tidak lebih besar dari
remaining, panggil fungsi pembantu dengan sisa nilai setelah membayar koin tersebut. - Simpan hasil terkecil yang bukan -1, lalu tambahkan satu untuk koin yang kamu bayarkan.
- Kembalikan jumlah tersebut, atau -1 jika semua koin tidak menghasilkan solusi. Jawabannya adalah
fewest(amount).
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)Rekursi dengan memoization
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Rekursi hanya menanyakan jumlah dari 0 sampai amount. Simpan setiap jawaban dalam array saat pertama kali kamu menghitungnya, lalu kembalikan nilai yang tersimpan saat jumlah itu ditanyakan lagi. Setiap jumlah diselesaikan sekali dengan perulangan pada koin: pekerjaan sebanyak O(amount × coins).
Panggilan tetap bertumpuk satu tingkat untuk setiap koin yang dibayarkan. Dengan koin bernilai 1, jumlah tingkatnya bisa mencapai 10^4, melebihi kapasitas tumpukan pemanggilan bawaan di banyak bahasa.
Algoritma
- Buat array
memodengan ruang untuk setiap nilai dari 0 hinggaamount, yang berisi penanda bahwa nilainya belum dihitung. - Di
fewest(remaining), kembalikan 0 untuk 0, dan kembalikanmemo[remaining]jika sudah berisi jawaban. - Jika tidak, coba setiap koin yang sesuai, seperti pada rekursi biasa, lalu simpan hasil terkecil ditambah satu.
- Simpan hasilnya, termasuk -1, di
memo[remaining]sebelum mengembalikannya. - Kembalikan
fewest(amount).
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)Pemrograman dinamis bottom-up untuk jumlah
Intuisi
Isi tabel fewest mulai dari 0 ke atas. Saat kamu mencapai total t, setiap total yang lebih kecil sudah ditentukan, jadi fewest[t] adalah satu lebih banyak daripada nilai fewest[t-c] terkecil di antara koin c yang muat.
Total yang tidak dapat dicapai dengan kombinasi koin apa pun menyimpan penanda amount + 1. Setiap koin bernilai setidaknya 1, jadi jawaban yang sebenarnya tidak pernah menggunakan lebih dari amount koin, dan penanda itu kalah dalam setiap perbandingan. Perulangan menggantikan rekursi, sehingga kedalaman tumpukan pemanggilan tidak pernah menjadi masalah.
Algoritma
- Buat
fewestdenganamount + 1entri, semuanya diatur ke penandaamount + 1, lalu aturfewest[0]ke 0. - Untuk setiap total
tdari 1 hinggaamount, periksa setiap koincdenganc ≤ t. - Jika
fewest[t-c] + 1lebih kecil daripadafewest[t], simpan nilai tersebut difewest[t]. - Setelah perulangan, kembalikan -1 jika
fewest[amount]masih menyimpan penanda, dan kembalikanfewest[amount]jika tidak.
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
Jebakan dan kasus tepi
- Mengambil koin terbesar terlebih dahulu. Dengan koin 3 dan 5 serta jumlah 9, cara ini membayar 5 dan 3, lalu terjebak pada 1 dan mengembalikan -1, padahal 3 + 3 + 3 bisa digunakan.
- Menggunakan bilangan bulat terbesar sebagai penanda. Menambahkan 1 ke bilangan itu menyebabkan overflow menjadi bilangan negatif, yang kemudian menang dalam setiap perbandingan. Gunakan
amount + 1. - Menambahkan 1 pada jalan buntu. Cabang yang mengembalikan -1, ditambah koin yang kamu bayarkan, menghasilkan 0 dan menang dalam setiap perbandingan. Lewati hasil -1.
- Melakukan rekursi sedalam
amounttingkat. Dengan koin bernilai 1 dan jumlah10^4, Python berhenti pada batas default 1000 tingkat, dan JavaScript, Dart, Ruby, serta R juga kehabisan stack. - Membaca
fewest[t-c]untuk koin yang nilainya lebih besar daripadat, sebelum awal tabel.
Pertanyaan yang sering diajukan3
Mengapa pendekatan greedy gagal untuk Coin Change?
Mengambil koin terbesar yang muat hanya aman untuk beberapa sistem koin, seperti sebagian besar mata uang yang digunakan saat ini. Dengan koin 1, 3, dan 4, cara ini membayar 6 dengan tiga koin, bukan dua, dan dengan koin 3 dan 5, cara ini sama sekali tidak bisa membayar 9. Pemrograman dinamis membandingkan setiap pilihan, jadi tidak ada sistem koin yang bisa mengecohnya.
Apa kompleksitas waktu dari Coin Change?
Solusi pemrograman dinamis membutuhkan waktu O(amount × coins) dan ruang O(amount): satu entri tabel untuk setiap jumlah, dan setiap koin diperiksa untuk setiap entri. Rekursi biasa tanpa memoization memiliki kompleksitas eksponensial terhadap jumlah tersebut.
Mana yang lebih baik untuk Coin Change, top-down atau bottom-up?
Keduanya melakukan pekerjaan O(amount × coins) yang sama. Rekursi top-down dapat bertingkat sedalam amount, sehingga tumpukan pemanggilan meluap untuk 10^4 dalam beberapa bahasa. Bottom-up mengisi tabel dengan perulangan, jadi tidak memiliki batas kedalaman dan menjadi pilihan yang lebih aman saat wawancara.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def coinChange(coins, amount):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
coins = [2, 5, 10] amount = 27
Output yang diharapkan
4