Coin Change

Given coin denominations and a target amount, find the minimum number of coins needed to make the amount (or the number of ways to make it). This is unbounded knapsack — you can use each coin unlimited times.

Minimum Coins (Unbounded Knapsack)

dp[a] = minimum coins needed to make amount a. For each coin c, try using it: dp[a] = min(dp[a], 1 + dp[a - c]).

C++ — minimum coins (forward loop = unbounded)

int coin_change(vector& coins, int amount) {
    vector dp(amount + 1, INT_MAX / 2);
    dp[0] = 0;

    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (a >= c)
                dp[a] = min(dp[a], 1 + dp[a - c]);
        }
    }
    return dp[amount] == INT_MAX / 2 ? -1 : dp[amount];
}

// Forward iteration = unbounded (each coin unlimited)
// Complexity: O(amount × |coins|)

Rust — minimum coins

fn coin_change(coins: &[i32], amount: i32) -> i32 {
    let amount = amount as usize;
    let mut dp = vec![i32::MAX / 2; amount + 1];
    dp[0] = 0;

    for a in 1..=amount {
        for &c in coins {
            if a >= c as usize {
                dp[a] = dp[a].min(1 + dp[a - c as usize]);
            }
        }
    }
    if dp[amount] == i32::MAX / 2 { -1 } else { dp[amount] }
}

💡 Forward = unbounded, Backward = 0/1

Iterating amount forward (a = 1..amount) lets you reuse the same coin multiple times — that's unbounded knapsack. Iterating backward (a = amount..1) ensures each coin is used at most once — that's 0/1 knapsack. Same 1D array, different loop direction.

Number of Ways to Make Change

C++ — count ways

int count_ways(vector& coins, int amount) {
    vector dp(amount + 1, 0);
    dp[0] = 1;

    for (int c : coins)                    // ← coins outer!
        for (int a = c; a <= amount; a++)  // ← forward (unbounded)
            dp[a] += dp[a - c];

    return dp[amount];
}

// Coins outer loop = combinations, not permutations.
// If amount were outer, (1,2) and (2,1) would both count.

📐 Coin order matters — combinations vs permutations

With coins outer, each coin is considered once → combinations (1+2 and 2+1 are the same). With amount outer, every coin is reconsidered at each amount → permutations (1+2 and 2+1 are both counted). Know the difference!

Key Takeaways