算法模式—动态规范

algorithm

动态规划(Dynamic Programming DP) 是一种将复杂问题分解为更小问题来解决的优化技术

动态规划和分而治之

动态规范

将问题分解成相互依赖的问题

分而治之

是把问题分解成为相互独立的子问题，然后组合形成答案

动态规划的基本步骤

• 定义子问题
• 实现要反复执行来解决子问题的部分
• 识别并求解出边界条件

动态规划可以解决的经典问题

最少硬币找零问题

function MinCoinChange(coins){
    var coins = coins;
    var cache = {};

    this.makeChange = function(amount){
        let me = this;
        if(!amount){
            return [];
        }
        if(cache[amount]){
            return cache[amount];
        }
        let min = [], newMin, newAmount;
        for (let i = 0; i < coins.length; i++) {
            let coin = coins[i];
            newAmount = amount - coin;
            if(newAmount >= 0){
                newMin = me.makeChange(newAmount);
            }
            if(
                newAmount >= 0 &&
                (newMin.length < min.length-1 || !min.length) &&
                (newMin.length || !newAmount)
            ){
                min = [coin].concat(newMin);
                console.log(`new Min ${min} for ${amount}`);
            }
        }

        return (cache[amount] = min);
    }
}

let minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36));

• makeChange 是一个递归函数
• amount 小于 0 就返回一个空数组
• cache 作为缓存，对于计算过的不在重新计算
• min 数组中保存着最佳方案
• newAmount 值会一直减少直到

new Min 1 for 1
new Min 1,1 for 2
new Min 1,1,1 for 3
new Min 1,1,1,1 for 4
new Min 1,1,1,1,1 for 5
new Min 5 for 5
new Min 1,5 for 6
new Min 1,1,5 for 7
new Min 1,1,1,5 for 8
new Min 1,1,1,1,5 for 9
new Min 1,1,1,1,1,5 for 10
new Min 5,5 for 10
new Min 10 for 10
new Min 1,10 for 11
new Min 1,1,10 for 12
new Min 1,1,1,10 for 13
new Min 1,1,1,1,10 for 14
new Min 1,1,1,1,1,10 for 15
new Min 5,10 for 15
new Min 1,5,10 for 16
new Min 1,1,5,10 for 17
new Min 1,1,1,5,10 for 18
new Min 1,1,1,1,5,10 for 19
new Min 1,1,1,1,1,5,10 for 20
new Min 5,5,10 for 20
new Min 10,10 for 20
new Min 1,10,10 for 21
new Min 1,1,10,10 for 22
new Min 1,1,1,10,10 for 23
new Min 1,1,1,1,10,10 for 24
new Min 1,1,1,1,1,10,10 for 25
new Min 5,10,10 for 25
new Min 25 for 25
new Min 1,25 for 26
new Min 1,1,25 for 27
new Min 1,1,1,25 for 28
new Min 1,1,1,1,25 for 29
new Min 1,1,1,1,1,25 for 30
new Min 5,25 for 30
new Min 1,5,25 for 31
new Min 1,1,5,25 for 32
new Min 1,1,1,5,25 for 33
new Min 1,1,1,1,5,25 for 34
new Min 1,1,1,1,1,5,25 for 35
new Min 5,5,25 for 35
new Min 10,25 for 35
new Min 1,10,25 for 36
[ 1, 10, 25 ]