You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

EXAMPLE 1:
INPUT: COINS = [1, 2, 5], AMOUNT = 11
OUTPUT: 3
EXPLANATION: 11 = 5 + 5 + 1

EXAMPLE 2:
INPUT: COINS = [2], AMOUNT = 3
OUTPUT: -1

Note: You may assume that you have an infinite number of each kind of coin.

Pseudo

  // define array and fill 
  // sort coins arr
  // set 0 index to 0
  // loop thru amount 
    // loop through coins in amount 
      // if coin is less than outer index 
        // assign min of arr index and 1 plus arr index minus inner index, to arr index
      // else break 

Solution

function coinChange(coins: number[], amt: number){
  // define array and fill 
  let arr = new Array(amt+1).fill(Infinity)
  // sort coins arr
  let coinsSorted = coins.sort((a,b)=>a-b)
  // set 0 index to 0
  arr[0] = 0
  // loop thru amount 
  let i=0
  while(i<=amt){
    // loop through coins in amount 
    let coin: number
    for (coin of coins){
      // if coin is less than outer index 
      if(coin<=i){
        // assign min of arr index and 1 plus arr index minus inner index, to arr index
        arr[i] = Math.min(arr[i], 1+arr[i-coin])
      }
      // else break 
      else{
        break
      }

    }
    i++
  }
  // if arr amt less Inf then arr amt else -1
  return amt<Infinity ? arr[amt] : -1
  
}
const coins = [1, 2, 5], amount = 11