Algoritmalar
en

Coin Change

Dynamic Programming O(n · amount) O(n · amount)

Fewest coins that sum to a target amount, given unlimited supply of each denomination.

c\a0123456
∅·······
1·······
3·······
4·······
Coins134amount 6
1/57

Amount 0 costs nothing.

Invariantdp[i][a] is the fewest coins making a from the first i denominations (∞ if it cannot be made).

coin-change.c
#define INF 1000000
 
int min(int a, int b) { return a < b ? a : b; }
 
int coinChange(int coins[], int n, int amount) {
    int dp[n + 1][amount + 1];
 
    for (int i = 0; i <= n; i++) {
        for (int a = 0; a <= amount; a++) {
            if (a == 0)
                dp[i][a] = 0;
            else if (i == 0)
                dp[i][a] = INF;
            else if (coins[i - 1] > a)
                dp[i][a] = dp[i - 1][a];
            else
                dp[i][a] = min(dp[i - 1][a],
                               dp[i][a - coins[i - 1]] + 1);
        }
    }
    return dp[n][amount];
}

How Coin Change works

dp[i][a] = fewest coins for amount a using the first i denominations: skip the coin, or use it once and stay in the same row (unlimited supply). ∞ marks unreachable amounts.

When to use it

Making change, minimal-resource combinations; the template for unbounded knapsack problems.