Hard dynamic programming

Exact change

A vending machine owes you change. Pay it out in as few coins as possible, and find out where greedy goes wrong.

Write minCoins(coins, amount): coins lists the coin values you have (as many of each as you like). Return the fewest coins that add up to exactly amount, or -1 if it cannot be done. An amount of 0 takes 0 coins.

Build a table dp where dp[a] is the fewest coins for amount a. Call show(row) as it fills, with unreachable amounts drawn as 0, and the stage draws the table as bars. For big amounts, showing every few entries is plenty.

Example: minCoins([1, 2, 5], 11) returns 3 (5 + 5 + 1). minCoins([1, 3, 4], 6) returns 2 (3 + 3), even though taking the biggest coin first gives 4 + 1 + 1.

Tests you can see

minCoins([1,2,5], 11)3
minCoins([2], 3)-1
minCoins([1,3,4], 6)2

More tests are hidden. The server runs them all before a time counts.

Call show() while your code works and the run plays back here.

javascriptminCoins()

function minCoins(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  // fill dp[1..amount] from smaller amounts, show(...) as you go
  return -1;
}

function minCoins(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  // fill dp[1..amount] from smaller amounts, show(...) as you go
  return -1;
}

Tab indents · Cmd/Ctrl+Enter runs