Coin Change

Coin Change

There are unlimited coins with denominations 2, 5 and 7. An item costs 27. How can the price be paid exactly using the fewest coins?

To minimize the number, perhaps use large coins first: 7 + 7 + 7 + 5 = 26. Hmm…

Try changing the strategy: use large coins, then finish using one denomination if possible. 7 + 7 + 7 + 2 + 2 + 2 = 27, using six coins. Surely that is right…

But the correct answer is 7 + 5 + 5 + 5 + 5 = 27, using five coins.

States anchor a dynamic-programming solution. Two ideas help define a state: the last step and the subproblem.

Even before finding the optimum, we know that an optimal solution uses k coins $a_1,a_2,\dots,a_k$ whose values sum to 27. A last coin $a_k$ must exist. The earlier coins sum to $27-a_k$. For the overall solution to be optimal, the number of coins for $27-a_k$ must also be minimal.

The problem becomes finding the fewest coins for $27-a_k$. This is a smaller subproblem.

Let F(x) be the minimum number of coins needed for x. The last coin can only be 2, 5 or 7:

• If $a_k$ is 2, this candidate uses F(27−2) + 1 coins, including the final 2.

• If $a_k$ is 5, this candidate uses F(27−5) + 1 coins, including the final 5.

• If $a_k$ is 7, this candidate uses F(27−7) + 1 coins, including the final 7.

Thus:

Coin change: recursion

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

static int min_int(int a, int b) {
    return a < b ? a : b;
}

int get_min_coins_recursive(int *coins, int coin_num, int price) {
    if (price <= 0) {
        return 0;
    }

    int min_coins = INT_MAX;

    for (int i = 0; i < coin_num; i++) {
        if (price >= coins[i]) {
            int previous = get_min_coins_recursive(coins, coin_num, price - coins[i]);
            if (previous != INT_MAX) {
                min_coins = min_int(previous + 1, min_coins);
            }
        }
    }

    return min_coins;
}

Another component of dynamic programming is the transition equation:

Consider the initial conditions and boundaries. If an amount i cannot be formed, define $F[i]=\infty$. Negative remaining amounts are also impossible:

The initial state is F[0] = 0, since no coins are needed to form zero.

Coin change: dynamic programming

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

static int min_int(int a, int b) {
    return a < b ? a : b;
}

int get_min_coins_dp(int *coins, int coin_num, int price) {
    int dp[price + 1];
    dp[0] = 0;

    for (int i = 1; i <= price; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < coin_num; j++) {
            if (i >= coins[j] && dp[i - coins[j]] != INT_MAX) {
                dp[i] = min_int(dp[i - coins[j]] + 1, dp[i]);
            }
        }
    }

    return dp[price];
}

Denominations are positive integers and the amount is nonnegative. For an impossible amount, Python returns ∞; C, C++ and Java return the maximum value of their integer type.