Coin Change

Problem

Given an array of coin denominations and a target amount, return the fewest number of coins needed to make that amount. Return -1 if it cannot be made.

Approach

Bottom-up DP. dp[a] holds the minimum coins for amount a. For each amount from 1..target, try every coin and take the min.

When to Use

Classic "minimum cost to reach target" DP. Any problem where you choose from a set of options to reach a goal with minimum steps/cost. Variations: unbounded knapsack, minimum operations.

Complexity

Time	O(amount * len(coins))
Space	O(amount)

Implementation

SolutionTestsChallenge

coin_change

Coin Change — minimum coins to make amount.

Problem

Given an array of coin denominations and a target amount, return the fewest number of coins needed to make that amount. Return -1 if it cannot be made.

Approach

Bottom-up DP. dp[a] holds the minimum coins for amount a. For each amount from 1..target, try every coin and take the min.

When to use

Classic "minimum cost to reach target" DP. Any problem where you choose from a set of options to reach a goal with minimum steps/cost. Variations: unbounded knapsack, minimum operations.

Complexity

Time: O(amount * len(coins)) Space: O(amount)

coin_change

coin_change(coins: Sequence[int], amount: int) -> int

Return the minimum number of coins to make amount, or -1.

coin_change([1, 5, 10, 25], 30) 2 coin_change([2], 3) -1

Source code in src/algo/dp/coin_change.py

def coin_change(coins: Sequence[int], amount: int) -> int:
    """Return the minimum number of coins to make *amount*, or -1.

    >>> coin_change([1, 5, 10, 25], 30)
    2
    >>> coin_change([2], 3)
    -1
    """
    if amount < 0:
        return -1
    if amount == 0:
        return 0

    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)

    return dp[amount] if dp[amount] <= amount else -1

tests/dp/test_coin_change.py

"""Tests for coin change."""

from algo.dp.coin_change import coin_change


class TestCoinChange:
    def test_basic(self) -> None:
        assert coin_change([1, 5, 10, 25], 30) == 2

    def test_standard_example(self) -> None:
        assert coin_change([1, 2, 5], 11) == 3

    def test_impossible(self) -> None:
        assert coin_change([2], 3) == -1

    def test_zero_amount(self) -> None:
        assert coin_change([1], 0) == 0

    def test_single_coin_exact(self) -> None:
        assert coin_change([3], 9) == 3

    def test_large_denomination(self) -> None:
        assert coin_change([1, 2, 5], 100) == 20

Implement it yourself

Run: just challenge dp coin_change

Then implement the functions to make all tests pass. Use just study dp for watch mode.

Reveal Solution

coin_change

Coin Change — minimum coins to make amount.

Problem

Given an array of coin denominations and a target amount, return the fewest number of coins needed to make that amount. Return -1 if it cannot be made.

Approach

Bottom-up DP. dp[a] holds the minimum coins for amount a. For each amount from 1..target, try every coin and take the min.

When to use

Classic "minimum cost to reach target" DP. Any problem where you choose from a set of options to reach a goal with minimum steps/cost. Variations: unbounded knapsack, minimum operations.

Complexity

Time: O(amount * len(coins)) Space: O(amount)

coin_change

coin_change(coins: Sequence[int], amount: int) -> int

Return the minimum number of coins to make amount, or -1.

coin_change([1, 5, 10, 25], 30) 2 coin_change([2], 3) -1

Source code in src/algo/dp/coin_change.py

def coin_change(coins: Sequence[int], amount: int) -> int:
    """Return the minimum number of coins to make *amount*, or -1.

    >>> coin_change([1, 5, 10, 25], 30)
    2
    >>> coin_change([2], 3)
    -1
    """
    if amount < 0:
        return -1
    if amount == 0:
        return 0

    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)

    return dp[amount] if dp[amount] <= amount else -1