You're given an integer total and a list of integers called coins. The variable coins hold a list of coin denominations, and total is the total amount of money. You have to find the minimum number of coins that can make up the total amount by using any combination of the coins.

coin-change.js

export function coinChange(coins, total) {
  // we make a total + 1 counter,
  // so later when we need to "ask" this array for a subproblem solution
  // it will look more natural, counter[total] (give me solution for total),
  // instead of doing -1 every time for index offset (counter[total-1])
  const counter = Array(total + 1).fill(null);
  // your code will replace this placeholder return statement
  return coinsChangeRec(coins, total, counter);
}

function coinsChangeRec(coins, total, counter) {
  // base case: if total === 0, the amount of coins to reach the total is 0
  if (total === 0) {
    return 0;
  }
  // base case: if total less than zero, no solution
  if (total < 0) {
    return -1;
  }
  // if we already have a solution for the subproblem, return in
  if (counter[total]) {
    return counter[total];
  }
  // in this variable we hold the minimum amount of coins needed to reach the total,
  // on this iteration
  let min = null;
  for (let i = 0; i < coins.length; ++i) {
    // at this point we are considering this single coin
    const coin = coins[i];
    // if we subtract this coin's value from total, we get a remainder of total
    // for the remainder we recursively calculate the min amount of tokens
    const result = coinsChangeRec(coins, total - coin, counter);
    if (result >= 0 && (!min || result < min)) {
      // we need to add 1
      // since result is min amount of coins needed to reach (total-coin), not just total
      // we can reach total from (total-coin) by adding our current coin we're at
      // so we do +1
      min = result + 1;
    }
  }
  // record the subproblem solution
  counter[total] = min ?? -1;
  return counter[total];
}

// tc:
// the depth of the recursion tree is total and each recursion call spawns coins.length calls,
// so is it O(coins.length ^ total),
// but because of the dp, we solve each total value subproblem once for each coin, so it's O(coins.length * total)
// sc: depth of the recursion tree is total, so O(total)