13.2 【动态规划】js解决硬币找零问题

动态规划与分治法不同之处在于分治法是将整体转变为数个相对独立的子问题，求解后组合

而动态规划则是将整体变为相互关联的子问题，通过整体的思想求解。

还是直接po代码吧

'use strict';

class minChangeQues {
    constructor (coins) {
        this.coins = coins
        this.cache = {}
    }

    changeCoins (amount) {
        // me 为整个class
        let me = this
        if (this.cache[amount]) {
            return this.cache[amount]
        }
        let min = [], newMin, newAmount
        for(let i in this.coins) {
            let coin = this.coins[i]
            newAmount = amount - coin
            if (newAmount >= 0) {
                newMin = me.changeCoins(newAmount)
            }
            if (newAmount >= 0 && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin)
            }
        }
        return (this.cache[amount] = min)
    }
}

let temp = new minChangeQues([1,5,10,25])
console.log(temp.changeCoins());