Skip to content

Coin Change

Coin problems use DP over amounts or over the set of coin types. Two common targets: minimum number of coins to reach a sum, or number of ways to make a sum (order may or may not matter).

Minimum coins (unbounded supply)

Infinite copies of each denomination. dp[x] = minimum coins to make sum x, or infinity if impossible.

Transition: for each coin c, dp[x] = min(dp[x], dp[x - c] + 1) for x >= c.

#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int minCoinsUnbounded(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (x >= c) dp[x] = min(dp[x], dp[x - c] + 1);
    return dp[amount] >= INF ? -1 : dp[amount];
}

Count ways (unbounded, combinations)

Often: ways to form amount where order of coins does not matter (iterate coin types outer loop so each combination is counted once).

#include <vector>
using namespace std;

long long countWaysUnbounded(const vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)
        for (int x = c; x <= amount; x++)
            dp[x] += dp[x - c];
    return dp[amount];
}

Swapping loops (amount outer, coin inner) typically counts ordered compositions—know which variant the statement asks for.

Each coin at most once (subset sum)

Whether some subset sums to T: iterate coins, update dp[x] backwards so each coin is used once.

#include <vector>
using namespace std;

bool canSumWithEachCoinOnce(const vector<int>& coins, int T) {
    vector<bool> dp(T + 1, false);
    dp[0] = true;
    for (int c : coins)
        for (int x = T; x >= c; x--)
            dp[x] = dp[x] || dp[x - c];
    return dp[T];
}

See Knapsack for value maximization with the same 0/1 loop order.