Dynamic ProgrammingPemulaFase C–FE1E5

COIN CHANGE

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.

Example use case

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

Syllabus

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

Objectives

·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

How It Works

·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

Prerequisites

·Array
·Rekursi atau perulangan

Real-World Uses

·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

Complexity O(nominal x jumlah jenis koin)