Coin change

Fewest coins needed to make an amount. A case where the greedy choice gives the wrong answer.

Time O(amount × coins)Space O(amount)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

dp[x] is the fewest coins that make x. To make x, try each coin c as the last coin used: that costs one coin plus the best way to make x - c.

Code

C++PythonC#

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

def coin_change(coins: list[int], amount: int) -> int:
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] != INF:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

public static int CoinChange(int[] coins, int amount) {
    var dp = new int[amount + 1];
    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        foreach (int c in coins)
            if (c <= x && dp[x - c] != int.MaxValue)
                dp[x] = Math.Min(dp[x], dp[x - c] + 1);
    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}

Tips

With coins 1, 3, 4 and amount 6, greedy takes 4 + 1 + 1 (three coins). DP finds 3 + 3 (two coins).
Infinity marks amounts that cannot be made.

In the .NET library

int.MaxValue + 1 wraps around to a large negative number in C#. That is why the code checks dp[x - c] != int.MaxValue before adding 1.