Pemrograman DinamisPemulaFase C–FE1E5

Coin Change (DP)

Coin Change mencari jumlah koin MINIMUM untuk suatu nominal. Dynamic Programming mengisi dp dari nilai kecil ke besar: dp[v] = 1 + min(dp[v - tiap koin]). Telusur balik menunjukkan koin mana yang dipakai. Relatable lewat masalah kembalian.

Contoh kasus

Mesin kasir menghitung kembalian dengan jumlah lembar atau keping uang paling sedikit.

Silabus

Coin Change mencari jumlah koin paling sedikit untuk suatu nominal dengan membangun jawaban dari nilai kecil ke besar.

Tujuan Belajar

·Memahami cara memecah nominal besar menjadi sub-nominal kecil
·Menjelaskan rumus dp[v] = 1 + min(dp[v - koin])
·Menerapkan DP untuk menghitung kembalian paling hemat

Cara Kerja

·Buat tabel dp berukuran nominal + 1, isi dp[0] = 0
·Untuk tiap nilai v dari kecil ke besar, coba semua jenis koin
·Ambil dp[v] = 1 + nilai minimum dari dp[v - koin] yang valid
·Simpan koin mana yang dipakai agar bisa ditelusuri balik
·dp pada nominal akhir adalah jumlah koin minimum

Prasyarat

·Array
·Rekursi atau perulangan

Contoh Nyata

·Mesin kasir menghitung kembalian dengan lembar uang paling sedikit
·Fitur split bill membagi tagihan jadi pecahan uang yang praktis
·Menyusun top-up pulsa dari kombinasi voucher termurah

Kompleksitas O(nominal x jumlah jenis koin)