DP Tanpa Batas & Pertukaran Koin
Menggunakan item berapa kali pun
DP Tanpa Batas & Pertukaran Koin adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Barang Tak Terbatas
Dalam ransel tak terbatas, setiap barang dapat diambil sebanyak yang Anda inginkan. Bayangkan koin dalam mesin penjual otomatis, bukan tumpukan barang yang jumlahnya tetap.
Satu Perubahan Kecil
Dibandingkan dengan 0/1, hanya arah perulangannya yang berubah. Untuk barang tak terbatas, Anda menelusuri kapasitas secara maju, dari kecil ke besar.
Penggunaan Kembali ke Arah Maju adalah Intinya
Saat bergerak maju, dp[w - coin] mungkin sudah mencakup koin yang sama. Penggunaan kembali yang disengaja inilah yang memungkinkan Anda mengambilnya lagi.
Berkenalan dengan Penukaran Koin
Masalah klasik penukaran koin meminta jumlah koin paling sedikit yang totalnya sama dengan suatu jumlah. Ini adalah DP tak terbatas dengan nilai minimum, bukan maksimum.
Tentukan Keadaannya
Misalkan dp[a] adalah jumlah koin paling sedikit yang diperlukan untuk membentuk jumlah a. Mulailah dengan dp[0] = 0 karena nol tidak memerlukan koin.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Gunakan Tak Terhingga untuk yang Mustahil
Jumlah yang tidak dapat dijangkau dimulai dengan nilai tak terhingga. Jika suatu jumlah tetap tak terhingga pada akhir proses, tidak ada kombinasi koin yang dapat membentuknya.
Transisinya
Untuk setiap koin, coba perbaiki setiap jumlah yang dapat dicapainya. Gunakan satu koin lebih banyak daripada jumlah yang lebih kecil yang tersisa.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Mengapa Urutan Maju
Menelusuri jumlah dari kecil ke besar memungkinkan dp[a - coin] sudah menghitung koin ini. Dengan cara itulah satu koin dapat berkontribusi beberapa kali.
Hitung Banyak Cara sebagai Gantinya
Ganti min+1 dengan penjumlahan untuk menghitung banyak cara membentuk setiap jumlah. Perulangan koin di luar mencegah urutan dihitung dua kali.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Baca Hasilnya
Jawaban Anda berada di dp[amount]. Pada versi minimum, nilai tak terhingga berarti target tidak mungkin dibentuk.
0/1 dan Tak Terbatas
Ingat satu pergantian ini: kapasitas mundur berarti setiap barang digunakan sekali, sedangkan arah maju berarti penggunaannya tidak terbatas. Tabelnya sama, tetapi arah penelusurannya berlawanan.
Pemeriksaan Cepat
Uji hal yang membuat ransel menjadi tak terbatas.
Rangkuman
Anda mengubah perulangan menjadi maju untuk penggunaan kembali tanpa batas dan membuat penukaran koin dengan nilai minimum untuk jumlah koin paling sedikit atau penjumlahan untuk total cara. 💰
Belajar Coding Interview Prep dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Pertanyaan yang Sering Diajukan
Apakah pelajaran “DP Tanpa Batas & Pertukaran Koin” gratis?
Ya — teks lengkap “DP Tanpa Batas & Pertukaran Koin” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “DP Tanpa Batas & Pertukaran Koin”?
Menggunakan item berapa kali pun Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “DP Tanpa Batas & Pertukaran Koin” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Knapsack 0/1: Ambil atau Tinggalkan
- Knapsack dengan Optimasi Ruang
- DP Tanpa Batas & Pertukaran Koin
- Jumlah Subset & Partisi