JavaScript/Dynamic-Programming/CoinChange.js at master · TheAlgorithms/JavaScript · GitHub

33 lines (33 loc) · 898 Bytes

/**

* @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

}

Expand file tree