Coin change adalah salah satu DP paling fundamental dengan dua variasi utama: minimum koin untuk membentuk sebuah nilai, dan jumlah cara berbeda untuk membentuknya. Kedua variasi menggunakan state yang sama tetapi transisi berbeda — satu memaksimalkan, satu menjumlahkan. Pada Chapter ini kita akan membedah kedua variasi, menangani kasus mustahil (impossible), dan menjelaskan perbedaan antara 0/1 (unbounded) coin change dan bounded coin change.

Aturan: Dua Variasi #

Variasi 1 — Minimum koin: diberikan koin dengan denominasi coins[] dan target amount, cari jumlah minimum koin untuk membentuk tepat amount. Bila tidak mungkin, kembalikan -1.

Variasi 2 — Jumlah cara: hitung berapa cara berbeda untuk membentuk tepat amount (urutan koin tidak diperhatikan).

Pada bagian ini kita fokus pada unbounded coin change — setiap koin boleh dipakai berulang kali.

Mekanisme: Transisi dan Base Case #

State: dp[a] — minimum koin (atau jumlah cara) untuk membentuk nilai a.

Transisi minimum: untuk setiap koin c, bila a >= c maka dp[a] = min(dp[a], dp[a-c] + 1).

Transisi counting: dp[a] += dp[a-c] untuk setiap koin c dengan a >= c.

Base case: dp[0] = 0 untuk minimum (0 koin untuk nilai 0), dp[0] = 1 untuk counting (satu cara: himpunan kosong).

Penanganan impossible: inisialisasi dp dengan INT_MAX (minimum) atau 0 (counting). Bila dp[amount] tetap INT_MAX, mustahil.

Kode: Minimum Koin (Unbounded) #

cpp 
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

int min_coins(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int a = 1; a <= amount; ++a) {
        for (int c : coins) {
            if (c <= a && dp[a - c] != INT_MAX) {
                dp[a] = std::min(dp[a], dp[a - c] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    std::vector<int> coins = {1, 5, 10, 25};
    for (int amount : {0, 7, 11, 63, 100}) {
        std::cout << "Min koin untuk " << amount << " = "
                  << min_coins(coins, amount) << '\n';
    }
    // Kasus mustahil
    std::vector<int> coins2 = {2, 4};
    std::cout << "Min koin untuk 7 dengan {2,4} = "
              << min_coins(coins2, 7) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Min koin untuk 0 = 0
Min koin untuk 7 = 3
Min koin untuk 11 = 2
Min koin untuk 63 = 6
Min koin untuk 100 = 4
Min koin untuk 7 dengan {2,4} = -1
  1. Baris std::vector<int> dp(amount + 1, INT_MAX);: inisialisasi semua nilai ke INT_MAX (belum tercapai). Pilih sentinel besar agar min tidak salah.
  2. Baris dp[0] = 0;: base case — 0 koin untuk nilai 0.
  3. Baris if (c <= a && dp[a - c] != INT_MAX): dua syarat — koin muat, dan sub-masalah a-c bisa tercapai.
  4. Baris dp[a] = std::min(dp[a], dp[a - c] + 1);: transisi inti. dp[a-c]+1 artinya “ambil koin c, sisanya butuh dp[a-c] koin”.
  5. Hasil 11 → 2: 10 + 1 = 2 koin. Hasil 63 → 6: 25+25+10+1+1+1 = 6 koin.
  6. Hasil 7 dengan {2,4} → -1: 7 ganjil, tidak bisa dibentuk dari genap. INT_MAX dipertahankan, dikembalikan sebagai -1.

Kode: Jumlah Cara (Unbounded, Tanpa Urutan) #

Untuk counting tanpa memperhatikan urutan, kita harus loop koin di luar dan nilai di dalam. Ini mencegah duplikat akibat urutan berbeda:

cpp 
#include <iostream>
#include <vector>

long long count_ways(const std::vector<int>& coins, int amount) {
    std::vector<long long> dp(amount + 1, 0);
    dp[0] = 1;  // satu cara untuk membentuk 0: himpunan kosong
    for (int c : coins) {
        for (int a = c; a <= amount; ++a) {
            dp[a] += dp[a - c];
        }
    }
    return dp[amount];
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    for (int amount : {3, 5, 10, 20}) {
        std::cout << "Jumlah cara untuk " << amount << " = "
                  << count_ways(coins, amount) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Jumlah cara untuk 3 = 2
Jumlah cara untuk 5 = 4
Jumlah cara untuk 10 = 10
Jumlah cara untuk 20 = 29
  1. Baris for (int c : coins) { for (int a = c; a <= amount; ++a) {...} }: urutan loop penting! Loop koin di luar, nilai di dalam, menghasilkan kombinasi tanpa urutan (1+2 dihitung sekali, tidak juga 2+1).
  2. Baris dp[a] += dp[a - c];: transisi counting. Untuk setiap koin c, tambahkan cara membentuk a-c ke dp[a].
  3. Hasil 5 → 4: 5; 2+2+1; 2+1+1+1; 1+1+1+1+1. Total 4 cara. Sesuai.

Loop dengan Urutan vs Tanpa Urutan #

cpp 
// Tanpa urutan (kombinasi): koin di luar
for (int c : coins)
    for (int a = c; a <= amount; ++a)
        dp[a] += dp[a - c];

// Dengan urutan (komposisi): nilai di luar
for (int a = 1; a <= amount; ++a)
    for (int c : coins)
        if (c <= a) dp[a] += dp[a - c];
PolaUrutan penting?Contoh amount=3, coins={1,2}Hasil
Koin di luarTidak{1+1+1, 1+2}2
Nilai di luarYa{1+1+1, 1+2, 2+1}3

Bounded Coin Change (0/1) #

Bila setiap koin hanya boleh dipakai sekali, masalah berubah menjadi subset-sum. Pendekatan DP 2D: dp[i][a] = boleh bentuk a dari koin 0..i-1 (masing-masing maksimal sekali).

cpp 
#include <iostream>
#include <vector>

bool can_form_bounded(const std::vector<int>& coins, int target) {
    int n = static_cast<int>(coins.size());
    std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(target + 1, false));
    for (int i = 0; i <= n; ++i) dp[i][0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int a = 0; a <= target; ++a) {
            dp[i][a] = dp[i - 1][a];  // lewati koin i-1
            if (a >= coins[i - 1]) {
                dp[i][a] = dp[i][a] || dp[i - 1][a - coins[i - 1]];
            }
        }
    }
    return dp[n][target];
}

int main() {
    std::vector<int> coins = {3, 34, 4, 12, 5, 2};
    for (int t : {9, 13, 100}) {
        std::cout << "Subset sum " << t << " = "
                  << (can_form_bounded(coins, t) ? "YA" : "TIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Subset sum 9 = YA
Subset sum 13 = TIDAK
Subset sum 100 = TIDAK
  1. Baris std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(target + 1, false));: tabel DP 2D. dp[i][a] = “apakah ada subset dari coins[0..i-1] dengan total a?”.
  2. Baris for (int i = 0; i <= n; ++i) dp[i][0] = true;: base case — total 0 selalu bisa (himpunan kosong).
  3. Baris dp[i][a] = dp[i - 1][a];: opsi lewati koin i-1.
  4. Baris if (a >= coins[i - 1]) dp[i][a] = dp[i][a] || dp[i - 1][a - coins[i - 1]];: opsi ambil koin i-1 (mengurangi target sebesar nilai koin).
  5. Hasil 9 → YA: subset {4, 5}. 13 → TIDAK karena tidak ada kombinasi yang menghasilkan tepat 13. 100 → TIDAK karena total seluruh koin hanya 60.

Optimasi Ruang pada Bounded Coin Change #

Karena dp[i][a] hanya bergantung pada dp[i-1][*], kita bisa menggunakan array 1D. Loop a dari besar ke kecil agar tidak memakai koin yang sama dua kali:

cpp 
std::vector<bool> dp(target + 1, false);
dp[0] = true;
for (int c : coins) {
    for (int a = target; a >= c; --a) {
        dp[a] = dp[a] || dp[a - c];
    }
}

Loop mundur menjamin dp[a-c] masih merujuk ke iterasi i-1, bukan iterasi i yang baru saja memakai koin c.

Tabel Ringkasan Kompleksitas #

VariasiStateWaktuRuangCatatan
Min koin (unbounded)dp[a]O(n · amount)O(amount)n = jumlah denominasi
Count ways (unbounded)dp[a]O(n · amount)O(amount)Loop koin di luar
Subset sum (0/1)dp[i][a]O(n · target)O(target) setelah optimasiLoop a mundur untuk 1D

Ringkasan #

  • Coin change memiliki dua variasi utama: minimum koin (optimasi) dan jumlah cara (counting).
  • Unbounded: koin boleh dipakai berulang. Bounded (0/1): setiap koin maksimal sekali.
  • Untuk counting tanpa urutan, loop koin di luar, nilai di dalam — hindari duplikat akibat permutasi.
  • Loop mundur pada 1D bounded coin change menjamin tidak memakai koin dua kali.
  • Selalu tangani kasus mustahil dengan sentinel seperti INT_MAX dan kembalikan -1 bila tidak tercapai.