Coin Change Problem

You've got a target amount $T$ and a list of coin denominations. Two related questions: what's the fewest coins that sum to $T$, and how many distinct combinations of coins sum to $T$?

Dynamic programming approach

Keep one array, $dp$, of length $T+1$. $dp[x]$ means different things depending on which version you're solving. For the fewest-coins question, $dp[x]$ is the minimum number of coins that sum to $x$. For the number-of-ways question, $dp[x]$ is the count of distinct combinations that sum to $x$. The algorithm is roughly the same in both cases. The only difference is the update rule for $dp$.

Time complexity

Each cell of $dp$ fills in constant time by looking back at smaller cells. With $n$ coin denominations and target $T$, the whole thing runs in $O(n\cdot T)$.

Implementation

def coin_change_min_coins(coins, T):
    """Minimum number of coins that sum to T, or -1 if impossible."""
    dp = [float('inf')] * (T + 1)
    dp[0] = 0
    for x in range(1, T + 1):
        for coin in coins:
            if x >= coin:
                dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[T] if dp[T] != float('inf') else -1


def coin_change_num_ways(coins, T):
    """Count of distinct coin combinations that sum to T."""
    dp = [0] * (T + 1)
    dp[0] = 1
    for coin in coins:
        for x in range(coin, T + 1):
            dp[x] += dp[x - coin]
    return dp[T]


# Example: target 11 with coins {1, 2, 5}.
coins, T = [1, 2, 5], 11
print(coin_change_min_coins(coins, T))   # 3   (e.g., 5 + 5 + 1)
print(coin_change_num_ways(coins, T))    # 11

Exercises

A full exercise set is available for this topic, structured as one worked example + 7 practice problems (across 7 surface contexts) + 2 pattern-resistant check problems.