Skip to content
Katabench
Try free
7 min read The Katabench team

Coin change with dynamic programming in C#

A greedy choice misses the best way to make eight. Build two dynamic programs for coin change and see why loop order changes the number of combinations.

A dispenser has tokens worth 1, 4 and 6 credits. Someone asks for 8 credits. Taking the largest token that fits gives 6 + 1 + 1. A person looking through the tray can do better with 4 + 4. The greedy dispenser makes the correct amount and still gets the answer wrong. It spent three tokens where two would do.

Coin change comes in two popular forms. The first asks how few tokens the dispenser needs. The second asks how many distinct combinations of tokens could make the amount. For this tray and this order the answers are two tokens and four combinations. Both problems fit a short dynamic program. They need different definitions for a table entry, and copying the loop order from one to the other can quietly change the question your program answers.

Assume throughout that the denominations are distinct positive whole numbers, the supply of every denomination is unlimited, and the requested amount is a nonnegative integer small enough for an array indexed by amount. A dispenser with only one 4-credit token is a different problem. Keep that distinction in mind when the example uses the same token value twice.

Find the fewest tokens by removing the last one

Pick any valid payout for 8 and remove one token. If it had value 6, the rest makes 2. If it had value 4, the rest makes 4. If it had value 1, the rest makes 7. To find the cheapest payout ending in a particular token, use the cheapest way to make the remainder and add one. If that remainder could use fewer tokens, swapping in the cheaper remainder would improve the whole payout too.

We can therefore solve the amounts from zero upward and try every possible last token at each amount. Every remainder is smaller because each token has positive value. The base case, zero tokens for amount zero, gives the recurrence somewhere to start. When no token can extend a reachable remainder to the target, the target is unreachable.

Three possible final tokens for a payout of 8
  1. Finish with 1

    1. 7 = 6 + 1
    2. + 1
    3. 3 tokens

    The best payout of 7 already needs two tokens.

  2. Finish with 4

    1. 4 = 4
    2. + 4
    3. 2 tokens

    The remainder takes one token, giving the cheapest payout.

  3. Finish with 6

    1. 2 = 1 + 1
    2. + 6
    3. 3 tokens

    The best payout of the remaining 2 uses two singles.

The implementation uses -1 for an unreachable amount. That marker stays out of the addition. Adding one to it would manufacture a zero-token payout. For example, with tokens worth 4 and 6 the amount 5 has two apparent candidates, a negative remainder after 6 and an unreachable remainder after 4. Neither is a payout.

C#
static int FewestTokens(int[] denominations, int amount)
{
    var fewest = new int[amount + 1];
    Array.Fill(fewest, -1);
    fewest[0] = 0;

    for (int total = 1; total <= amount; total++)
    {
        foreach (int token in denominations)
        {
            int remainder = total - token;
            if (remainder < 0 || fewest[remainder] == -1)
                continue;

            int candidate = fewest[remainder] + 1;
            if (fewest[total] == -1 || candidate < fewest[total])
                fewest[total] = candidate;
        }
    }
    return fewest[amount];
}

You can run the minimum calculation with the denominations in any order. Some payouts appear from more than one choice of final token. Both 6 + 1 and 1 + 6 can suggest two tokens for amount 7. Taking the smaller of two identical candidates still gives two. Counting them by addition would be a different matter.

Count each payout once by deciding which tokens it may use

Write down all four payouts for amount 8. There are eight singles, one 4 and four singles, two 4s, or one 6 and two singles. Handing the singles over first does nothing to change the contents of the tray. If a naive recursive count branches on every possible next token, it counts 6, 1, 1, 1, 6, 1 and 1, 1, 6 separately.

Give the denominations a fixed order. After processing the 4-credit denomination, let ways[total] mean the number of combinations using only 1s and 4s. Prior to that pass the array held combinations using only 1s. For each amount, the old value already covers payouts that use zero 4s. The payouts that use one or more 4s correspond exactly to the payouts for total - 4 after processing 4s. Remove one 4 to go in one direction, add it back to go the other way. These two groups are disjoint, so their counts can be added.

Count combinations by giving each one a single place to enter the table. A payout using a 6 first becomes possible in the pass that admits 6s. Rearranging its tokens never creates a new entry.

C#
static long CountPayouts(int[] denominations, int amount)
{
    var ways = new long[amount + 1];
    ways[0] = 1;

    foreach (int token in denominations)
    {
        for (int total = token; total <= amount; total++)
        {
            ways[total] = checked(ways[total] + ways[total - token]);
        }
    }
    return ways[amount];
}

There is one way to pay zero credits, the empty payout. This is why ways[0] starts at one. When a denomination is processed for the first time, the entry for that exact amount adds the empty payout with one token attached. Starting at zero would leave the whole array at zero forever, even for a tray containing singles.

The inner loop moves upward so ways[total - token] already includes combinations using the current token. During the pass for 4s, ways[4] becomes two because you can use either four singles or one 4. At amount 8 both can be extended with another 4. Together with the existing eight singles, that makes three combinations so far. The pass for 6s adds the payout made by attaching a 6 to the two singles, giving four. Walking downward through the amounts would read ways[4] before adding the first 4-credit token. You would lose the two-4 payout and effectively allow each denomination only once.

Use an amount small enough to audit

Try tokens of value 1 and 2 with a target of 3. The minimum is two. The combinations are 1 + 1 + 1 and 1 + 2, also two. If the counting method visits amounts first and tries every last token, it reports three because it also counts 2 + 1. A target of 2 would let that loop bug pass. There are no two distinct tokens that can trade places in a payout of 2. Picking an input that exercises the rule is the same skill used in boundary value analysis.

Both methods take O(amount × denominations) time and O(amount) space using fixed-width numbers. This makes the numeric amount an important part of the workload. Adding a digit to the amount can multiply the size of the table by ten while barely changing the size of the input file. Counting introduces another limit. Many denominations can produce more combinations than a long can hold. The checked addition reports an overflow if any table entry exceeds that bound. Use arbitrary-precision integers if exact larger counts are part of your contract, and budget for arithmetic on those larger values.

The two coin change katas in C# coding challenges let you run both definitions on the same tray. Try the zero amount first, then an unreachable amount, then 8 with the three denominations above. Once those results are right, the performance guide explains how to read the tests that make repeated recursive work visible on larger amounts.

Practice what you just read

More like this: C# coding challenges →

Get new katas and .NET tips in your inbox

A short note when fresh kata land, plus the C# and performance tricks behind the grading. No spam, unsubscribe anytime.