Room 04 · The Grind — 1-D Dynamic Programming

Coin Change

MEDIUM✓ CHIP-TIMEDLC #322 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: A set of coin denominations and a target amount — find the fewest coins that sum to exactly that amount, with unlimited coins of each kind, or report it's impossible.

A set of coin denominations arrives alongside a target amount, and an unlimited supply of each denomination is available to use.

The task is to reach the target amount exactly, using as few coins as possible from that unlimited supply, mixing denominations freely.

If no combination of the given coins can add up to the target exactly, that has to be signaled distinctly rather than returned as some default count.

denomination count is small; target amount up to a few thousand
coin values are positive integers, unlimited supply of each
coins may repeat and mix freely to reach the exact target
an unreachable target reports a distinct sentinel value

EX 01

coins = [1, 2, 5] · amount = 11

→ 3

classic mixed denominations

EX 02

coins = [2] · amount = 3

→ -1

odd target, only an even coin

EX 03

coins = [1] · amount = 0

→ 0

target already zero

The hintstake only what you need

HINT 1 THE NUDGE

Trying every combination of coins to hit the amount branches at every denomination, at every remaining amount — what does the fewest-coins answer for amount a actually need from smaller amounts?

HINT 2 THE STRUCTURE

The fewest coins to make amount a is one plus the fewest coins to make a minus some coin's value, minimized over every coin — and every amount smaller than a can be solved first.

HINT 3 ONE STEP FROM THE ANSWER

Build a table from 0 up to the target: dp[a] = 1 + the smallest dp[a - c] over every coin c ≤ a, with dp[0] = 0. Any amount that stays unreachable answers -1.

Coach's boardthe pattern, step by step

COINS FROM ZERO UPPATTERN · BOTTOM-UP AMOUNT DPcoins = [1, 3, 4] · amount = 6

STEP 1

dp[0] = 0 — zero coins needed for zero amount, the base case.

STEP 1 / 8 · ← → WORK TOO

The splitstwo paces, two languages

grind/coin-change.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [math.inf] * amount
        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] != math.inf else -1

TIME O(AMOUNT·K)SPACE O(AMOUNT)PYTHON · RACE PACE · 8 LN

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def fewest(remaining: int) -> float:
            if remaining == 0:
                return 0
            if remaining < 0:
                return math.inf
            best = math.inf
            for c in coins:                        # try every coin at every depth
                best = min(best, 1 + fewest(remaining - c))
            return best

        result = fewest(amount)
        return result if result != math.inf else -1

TIME O(K^AMOUNT)SPACE O(AMOUNT)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && dp[a - c] != Integer.MAX_VALUE) {
                    dp[a] = Math.min(dp[a], dp[a - c] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

TIME O(AMOUNT·K)SPACE O(AMOUNT)JAVA · RACE PACE · 15 LN

class Solution {
    public int coinChange(int[] coins, int amount) {
        int result = fewest(coins, amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int fewest(int[] coins, int remaining) {
        if (remaining == 0) {
            return 0;
        }
        if (remaining < 0) {
            return Integer.MAX_VALUE;
        }
        int best = Integer.MAX_VALUE;
        for (int c : coins) {                       // try every coin at every depth
            int sub = fewest(coins, remaining - c);
            if (sub != Integer.MAX_VALUE) {
                best = Math.min(best, 1 + sub);
            }
        }
        return best;
    }
}

TIME O(K^AMOUNT)SPACE O(AMOUNT)JAVA · TRAINING PACE · 23 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED