Marauder Bot

Problem

You are given a set of coin denominations and a target amount. Return the smallest number of coins that add up to exactly that amount, assuming you have an unlimited supply of each denomination. If no combination reaches the amount, return -1.

Example. With coins [1, 2, 5] and a target of 11, the best answer is 3 coins: 5 + 5 + 1.

Key idea

Greedily grabbing the largest coin first does not work in general: with coins [1, 3, 4] and a target of 6, greedy gives 4 + 1 + 1 (three coins) when 3 + 3 (two coins) is better. So instead, build the answer up from the smallest subtotals.

Define the best answer for every subtotal from 0 up to the target. The answer for 0 is 0 coins. For any larger subtotal, look at what happens if the last coin you place is denomination c: the remaining amount is the already-solved subtotal amount - c, so this choice costs one more coin than that subproblem. Take the minimum over every denomination that fits. Because each subtotal only depends on smaller ones, filling the table from small to large means every value you need is ready when you reach it.

Solution

function coinChange(coins: number[], amount: number): number {
  // A subtotal that stays at this sentinel was never reachable.
  const fewest = new Array<number>(amount + 1).fill(amount + 1);
  fewest[0] = 0;

  for (let subtotal = 1; subtotal <= amount; subtotal++) {
    for (const coin of coins) {
      if (coin <= subtotal) {
        // 1 coin here plus the best way to make the remainder
        fewest[subtotal] = Math.min(fewest[subtotal], fewest[subtotal - coin] + 1);
      }
    }
  }

  return fewest[amount] > amount ? -1 : fewest[amount]; // sentinel survived: amount is unreachable
}

Complexity

Time: O(amount × number of coins). One pass over each subtotal, trying every denomination.
Space: O(amount). One entry per subtotal.

Watch out for

Seed unreachable subtotals with a sentinel (such as amount + 1 or infinity) so a real coin count always beats "impossible," and translate a leftover sentinel at the target into -1.
The subtotal 0 must be 0 coins, not the sentinel; it is the base case every other value ultimately builds on.

Pattern

This is the "unbounded" flavor of the coin/knapsack family: unlimited reuse of each item and a running optimum over subtotals. The same table-building instinct (express a target in terms of a smaller already-solved target) carries over to problems like combination counting and word break.

Coin Change