Coin change

Overview

Coin change is two different questions that share one table shape. Minimum coins asks for the fewest coins summing to an amount; counting change asks how many distinct combinations reach it. Both index the table by amount — dp[a] is the answer for amount a — and build upward from dp[0]. What separates them is subtle and important: for counting, the loop order decides whether you count combinations or permutations. Putting coins in the outer loop counts each combination once; putting amount outside counts ordered sequences, which is usually not what was asked.

Why it matters

This is the canonical unbounded-knapsack shape, and it appears well beyond currency: making up a total from packet sizes, scheduling with repeatable units, counting ways to tile a length. It is also the clearest example of a DP where the loop order is part of the algorithm rather than a stylistic choice — a lesson that transfers directly to the 0/1 knapsack in the next lesson, where the order flips for the opposite reason.

Core concepts

Amount-indexed table. dp[0] is the base case — one way to make zero (use nothing), zero coins needed. Every larger amount is built from smaller ones.

Minimum coins. dp[a] = min over coins c <= a of (dp[a-c] + 1). Unreachable amounts must stay at a sentinel (a large INF), and you must guard against dp[a-c] being INF before adding one — otherwise INF+1 wraps into a small number and reports a bogus solution.

Counting combinations. dp[0] = 1, then for each coin (outer), for each amount (inner): dp[a] += dp[a-c]. Because a coin is fully processed before the next one begins, {1,2} and {2,1} are never counted separately.

Counting permutations. Swap the loops — amount outer, coin inner — and ordered sequences are counted instead. Same table, same recurrence, different meaning. Decide which the problem wants before writing the loops.

Unbounded reuse. Iterating the amount upward lets dp[a-c] already include coin c, which is exactly what "use each coin as many times as you like" means. The 0/1 variant flips this direction.

Overflow. Counting answers grow quickly — use long long (or the specified modulus).

Syntax notes

#include <stdlib.h>

/* fewest coins for amt, or -1 if unreachable */
int min_coins(const int *c, int nc, int amt) {
    const int INF = 1000000000;
    int *dp = malloc((size_t)(amt + 1) * sizeof *dp);
    if (!dp) return -1;
    dp[0] = 0;
    for (int a = 1; a <= amt; a++) {
        dp[a] = INF;
        for (int i = 0; i < nc; i++)
            if (c[i] <= a && dp[a - c[i]] != INF && dp[a - c[i]] + 1 < dp[a])
                dp[a] = dp[a - c[i]] + 1;      // guard INF before adding
    }
    int r = (dp[amt] == INF) ? -1 : dp[amt];
    free(dp);
    return r;
}

/* number of COMBINATIONS (coin loop outside) */
long long count_change(const int *c, int nc, int amt) {
    long long *dp = calloc((size_t)amt + 1, sizeof *dp);
    if (!dp) return -1;
    dp[0] = 1;
    for (int i = 0; i < nc; i++)              // coins OUTER  -> combinations
        for (int a = c[i]; a <= amt; a++)     // amount upward -> unlimited reuse
            dp[a] += dp[a - c[i]];
    long long r = dp[amt];
    free(dp);
    return r;
}

Key points:

• Coin loop outside = combinations; amount outside = permutations.
• Guard the INF sentinel before + 1, or unreachable amounts poison the table.
• calloc zeroes the counting table; dp[0] = 1 is the seed.

Lesson

Given coin denominations, two classic questions: the fewest coins to make an amount, and the number of combinations that make it. Both fill a table indexed by amount, but they differ in one crucial way — for counting combinations you must loop coins on the outside so each combination is counted once, not every ordering.

Code examples

#include <stdio.h>
#include <stdlib.h>
static int min_coins(const int *c,int nc,int amt){ int *dp=malloc((amt+1)*sizeof(int)); const int INF=1e9; dp[0]=0; for(int a=1;a<=amt;a++)dp[a]=INF; for(int a=1;a<=amt;a++)for(int i=0;i<nc;i++)if(c[i]<=a&&dp[a-c[i]]+1<dp[a])dp[a]=dp[a-c[i]]+1; int r=dp[amt]>=INF?-1:dp[amt]; free(dp); return r; }
static long long count_change(const int *c,int nc,int amt){ long long *dp=calloc(amt+1,sizeof(long long)); dp[0]=1; for(int i=0;i<nc;i++)for(int a=c[i];a<=amt;a++)dp[a]+=dp[a-c[i]]; long long r=dp[amt]; free(dp); return r; }
int main(void){
    int coins[]={1,2,5};
    printf("fewest coins for 11 (from {1,2,5}) = %d\n", min_coins(coins,3,11));
    printf("ways to make 5 = %lld\n", count_change(coins,3,5));
    return 0;
}

Line by line

Common mistakes

Greedy for min-coins (fails for odd denominations); wrong loop nesting for the count.

Debugging tips

Compiler errors and warnings:

• warning: comparison of integer expressions of different signedness — mixing int amounts with size_t; cast at the allocation.
• No warning for the wrong loop order — only a test against a known answer catches it.

Runtime symptoms:

• The count is far too high. Your loops are the wrong way round — you counted permutations. For coins {1,2}, amount 3: combinations = 2, permutations = 3.
• min_coins returns a small number for an impossible amount. You added 1 to the INF sentinel and it wrapped or compared as valid. Check dp[a-c] != INF first.
• Segfault at small amounts. The inner loop started below c[i], producing a negative index.
• Counts go negative. Overflow — use long long, or apply the modulus the problem specifies.
• dp[0] wrong. For counting it is 1; for min-coins it is 0. Mixing them up breaks everything downstream.

Technique: test with coins {1,2} and amount 3. Combinations = 2, permutations = 3 — the single fastest way to prove your loop order.

Memory safety

These implementations allocate, so ordinary heap rules apply on top of the DP logic:

• Check the allocation. malloc/calloc can return NULL; dereferencing it is a crash. Every path must handle it.
• Free on every exit path. Note the pattern above: capture the result into a local, free, then return. Returning dp[amt] directly after free would read freed memory.
• Validate amt first. A negative amt makes (amt + 1) small or negative and the cast to size_t enormous — a classic allocation-size wrap. Reject negatives before allocating.
• malloc gives garbage, calloc gives zeros. The min-coins table is fully overwritten so malloc is fine; the counting table is accumulated into, so it must start zeroed.
• Index bounds. dp[a - c[i]] is safe only because the loop starts at c[i]; a coin value of 0 or a negative coin would break that invariant — validate the coin list.

Real-world uses

Concrete uses: Vending machines and point-of-sale systems computing change. Splitting a payload across fixed packet sizes. Cash-drawer denominations planning. Counting the ways to tile a strip with pieces of given lengths. Resource planning where units are repeatable. The same unbounded shape drives "minimum number of perfect squares summing to n" and similar problems.

Professional best practices:

Beginner:

• Write down whether the problem wants combinations or permutations before writing the loops.
• Use a named INF sentinel and guard it explicitly.

Intermediate:

• Note that the greedy "take the largest coin" approach is correct only for canonical coin systems; for arbitrary denominations ({1,3,4}, amount 6) it fails and DP is required.
• Choose long long or apply the problem's modulus for counting variants — the numbers grow fast.
• Free the table on every exit path, including error paths.

Practice tasks

1. (Beginner) Minimum coins. Implement int min_coins(const int *c, int nc, int amt) returning -1 when the amount is unreachable. Requirements: guard the INF sentinel. Example: coins {1,3,4}, amount 6 → 2 (3+3), not 3 as greedy would give. Concepts: amount-indexed DP, sentinels.

2. (Beginner) Count combinations. Implement count_change with the coin loop outside. Example: coins {1,2}, amount 3 → 2. Concepts: loop order, dp[0] = 1.

3. (Intermediate) Show the difference. Write both loop orders and print both results for {1,2} and amount 3 (expect 2 and 3). Concepts: combinations vs permutations.

4. (Intermediate) Reconstruct the coins. Extend min_coins to also output which coins were used. Hint: store the chosen coin per amount in a parallel array and walk backwards from amt. Concepts: DP reconstruction.

Summary

Coin change indexes its table by amount and builds upward from dp[0]. For the minimum-coins variant, dp[a] = min(dp[a-c] + 1) with an INF sentinel that must be guarded before you add to it. For the counting variant, dp[0] = 1 and the loop order is the algorithm: coins in the outer loop counts combinations, amount in the outer loop counts permutations. Iterating amounts upward is what permits unlimited reuse of each coin — the direction flips in the 0/1 knapsack. Use long long for counts, validate the amount before allocating, and free the table on every exit path.

Practice with these exercises

• Fewest coins
• Count ways to make change