One Pager Cheat Sheet

• The task is to find the minimum number of coins that add up to a given denomination amount using dynamic programming, with a given set of coins of different denominations and an infinite supply of each one.
• This problem can be solved using an efficient dynamic programming algorithm to efficiently explore all possible combinations and find the one with a minimum number of coins.
• Boldly dynamic programming is used to define an array matrix M, whose size is N*(amount+1) to store the intermediate results of the coin change problem.
• The figure shows how the Matrix M is filled row by row, with each value in the cell equaling the minimum number of coins required to pay the amount, given the coin denomination for that row.
• Write code to solve the coin change problem in O(NT) time, where inf is the highest value of the coin denominations and -1 is returned if no combination is possible.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function coinChange(coins, amount) {

  // Each memo[i] is the least amount of coins

  // that can make the value equal to the index value.

  const memo = Array(amount + 1).fill(Infinity);

  memo[0] = 0;

​

  for (let i = 1; i <= amount; i++) {

    for (const coin of coins) {

      if (i - coin >= 0) {

        memo[i] = Math.min(memo[i], memo[i - coin] + 1);

      }

    }

  }

  return memo[amount] === Infinity ? -1 : memo[amount];

}

​

try {

  assert.equal(coinChange([2, 3, 5], 11), 3);

​

  console.log('PASSED: ' + 'First Test: coinChange([2, 3, 5], 11)');

} catch (err) {

  console.log(err);

}

​

try {

  assert.equal(coinChange([2, 3, 5, 7], 17), 3);

​

  console.log('PASSED: ' + 'Second Test: coinChange([2, 3, 5, 7]');

} catch (err) {

  console.log(err);

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.