CoinChange.js

/**
 * @params {Array} coins
 * @params {Number} amount
 */
export const change = (coins, amount) => {
 // Create and initialize the storage
 const combinations = new Array(amount + 1).fill(0)
 combinations[0] = 1
 // Determine the direction of smallest sub-problem
 for (let i = 0; i < coins.length; i++) {
 // Travel and fill the combinations array
 for (let j = coins[i]; j < combinations.length; j++) {
 combinations[j] += combinations[j - coins[i]]
 }
 }
 return combinations[amount]
}
/**
 * @params {Array} coins
 * @params {Number} amount
 */
export const coinChangeMin = (coins, amount) => {
 const map = { 0: 1 }
 for (let i = 1; i <= amount; i++) {
 let min = Infinity
 for (const coin of coins) {
 if (i < coin) continue
 min = Math.min(min, 1 + map[i - coin])
 }
 map[i] = min
 }
 return map[amount] === Infinity ? -1 : map[amount] - 1
}