Given a list of coins[] of different denominations with infinite supply of each of the coins. Find the minimum number of coins required to make the given sum. If it's not possible to make a change, return -1.

Hint

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

def count(coins, total):
  cache = [[0 for _ in range(total + 1)] for _ in range(len(coins))]

  for i in range(len(coins) - 1, -1, -1):
    for j in range(1, total + 1):
      take = float('inf')
      skip = float('inf')

      if j >= coins[i]:
        take = cache[i][j - coins[i]]
        
        if take != float('inf'):
          take += 1
        
      if i + 1 < len(coins):
        skip = cache[i + 1][j]

      cache[i][j] = min(take, skip)

  return cache[0][total]

coins = [25, 10, 5]
total = 30

coins.sort(reverse=True)

output = count(coins, total)

print(output if (output != float('inf')) else -1)

// Javascript implementation

function count(coins, sum) {
  const cache = [];

  for (let i = 0; i < coins.length; i++) {
    cache[i] = [];
    
    for (let j = 0; j< sum + 1; j++) {
      cache[i][j] = 0;
    }
  }

  for (let i = coins.length - 1; i >= 0; i--) {
    for (let j = 1; j < sum + 1; j++) {
      let take = Infinity;
      let skip = Infinity;

      if (j >= coins[i]) {
        take = cache[i][j - coins[i]];
        
        if (take != Infinity) {
          take += 1
        }
      }

      if (i + 1 < coins.length) {
        skip = cache[i + 1][j];
      }

      cache[i][j] = Math.min(take, skip);
    }
  }

  return cache[0][sum];
}

const coins = [25, 10, 5];
const sum = 30;

coins.sort((a, b) => b - a);

const output = count(coins, sum);

console.log((output !=  Infinity) ? output : -1);

Find minimum coins to make change (Tabulation)

Hint