web123456

Dynamic programming method for coin change problems (JS)

class MinCoinChange{ constructor(arr){ this.money = arr //Deposit of available change denominations this.length = arr.length // Number of change this.coinCount = [0] //Minimum number of coins used for $/i this.coinValue = [[]] List of least coins used for //i$ } makeChange(n){ for(let i = 1; i <= n ; i++){ let minCount = Infinity this.coinValue[i] = [] for(let j = 0;j<this.length;j++){ if(i >= this.money[j]){ if(minCount > this.coinMoney[i-this.money[j]]+1){ minCount = this.coinCount[i-this.money[j]]+1 this.coinValue[i] = JSON.parse(JSON.stringify(this.coinValue[i-this.money[j]])) this.coinValue[i].push(this.money[j]) } } } this.coinCount[i] = minCount } console.log(this.coinValue[n]) return this.coinCount[n] } } const minCoinChange = new MinCoinChange([1, 5, 10, 25]); console.log(minCoinChange.makeChange(36)) // [1, 10, 25] const minCoinChange2 = new MinCoinChange([1, 3, 4]); console.log(minCoinChange2.makeChange(6)) // [3, 3]