硬币找零问题的动态规划法（JS）
class MinCoinChange{
constructor(arr){
this.money = arr //存放可用零钱面值
this.length = arr.length //零钱数目
this.coinCount = [0] //i元所用最少硬币数
this.coinValue = [[]] //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]