Coin Change — Minimum Number of Coins

The problem

Implement `coinChangeMinimumNoOfWays(coins, sum)`: given coin denominations available in unlimited supply, return the fewest coins that add up to `sum` exactly. Unlike the counting version, the answer is a coin count, not a way count.

`coins = [1, 2, 5], sum = 11` returns `3` — `5 + 5 + 1`. `coins = [2], sum = 3` returns `Infinity`: no multiset of twos lands on an odd number, and this version reports that as `Infinity` rather than LeetCode's `-1`.

The approach

The grid and the recurrence are the unbounded knapsack's, with `Math.max` swapped for `Math.min` and the item's value swapped for a flat `1`. `memo[i][j] = Math.min(1 + memo[i][j - weights[i-1]], memo[i-1][j])` reads as 'either use this coin once more and pay one coin for the privilege, or stop considering it entirely'. The `i` on the include branch is the same unbounded-knapsack `i` — coin `i` stays available after being used — and it's still the only character separating this family from 0/1.

The base cases are where minimisation stops being a cosmetic swap. `memo[i][0] = 0` is unchanged and obvious: zero coins make zero. But `memo[0][j] = Infinity` is the opposite of every previous entry's row `0`. With no coins available, a positive sum isn't reachable at cost `0` — it isn't reachable at all, and `Infinity` is what makes that fact survive being passed through a `Math.min`. Seed it with `0` and the table cheerfully reports that every sum costs nothing.

The two seeding loops overlap at `memo[0][0]` again, and the order is load-bearing for the same reason as in `subsetSumProblem`. The `Infinity` row runs first, the zero column runs second, so `memo[0][0]` ends up `0` — correct, because no coins do make zero. Write them the other way round and the cell that every reachable path eventually bottoms out on is `Infinity`, which poisons the entire table with one assignment.

The row-`1` initialisation loop — `j % weights[0] === 0 ? j / weights[0] : Infinity` — is correct reasoning and unnecessary code. With only the first coin available, a sum is reachable iff it's a multiple of that coin, and the count is the quotient. But the main loop starts at `i = 1`, so it recomputes every one of those cells from `memo[0][j] = Infinity` and `memo[1][j - weights[0]]`, and arrives at exactly the same numbers. It's harmless and it's dead. It also reads `weights[0]` unguarded, so an empty `coins` array turns the whole row into `NaN` before the main loop overwrites it.

`Infinity` doing the arithmetic rather than a sentinel integer is what keeps this correct. `1 + Infinity` is `Infinity` in JavaScript, so an unreachable sub-sum stays unreachable no matter how many times it's added to. The same code with `Number.MAX_SAFE_INTEGER` as the marker would overflow past it and start returning enormous finite numbers that look like real answers — which is the exact bug the C++ version of this problem is famous for.

The solution

export function coinChangeMinimumNoOfWays(coins, sum) {
  return unboundedKanpsack(coins, sum);
}

function unboundedKanpsack(weights, capacity) {
  const memo = Array.from({ length: weights.length + 1 }, () =>
    Array(capacity + 1).fill(null),
  );

  // initialize the first column with 0
  for (let j = 0; j <= capacity; j++) {
    memo[0][j] = Infinity;
  }

  // initialize the first row with 0
  for (let i = 0; i <= weights.length; i++) {
    memo[i][0] = 0;
  }

  // initialize the second column with 0
  for (let j = 1; j <= capacity; j++) {
    let val;
    if (j % weights[0] == 0) {
      val = j / weights[0];
    } else {
      val = Infinity;
    }
    memo[1][j] = val;
  }

  // fill the memo table
  for (let i = 1; i <= weights.length; i++) {
    for (let j = 1; j <= capacity; j++) {
      if (weights[i - 1] <= j) {
        memo[i][j] = Math.min(1 + memo[i][j - weights[i - 1]], memo[i - 1][j]);
      } else {
        memo[i][j] = memo[i - 1][j];
      }
    }
  }

  // return the maximum value
  return memo[weights.length][capacity];
}

Time O(n * sum)Space O(n * sum)