菜鸟说动态规划

从我学习至今，我有三大心理阴影：递归、正则表达式、动态规划——这三个导致让我怀疑智商怀疑人生。

在这次假期刷题的时候，前两个似乎都已经不是问题了，就差动态规划——昨天不行random到一道题，一眼望着就是动态规划了——可是我不会啊。

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

题目来自LeetCode，本来是不准备写LeetCode的题了，全都在GitHub上了大家看看就行了，不过这题有助于让我们更好地理解（第一次理解）动态规划。

动态规划和一般递归的思路有点相似，递归就想数学归纳法，前一项与后面项的关系，而动态规划则是大问题与其子集小问题的关系。

因此，只有在小问题的解最优能推出大问题的解最优的情况才能用动态规划（也就是局部最优解和全局最优解的关系 ）。

动态规划的关键在于：如何写出状态转移方程。

有了状态转移方程，剩下的也就自然的有了（而且用的是迭代）。

在写状态转移方程上，我们可以举个例子在进行推导，但在推导之前，还有更重要的事情要做：

他的局部最优解是否能满足全局最优解

答案是肯定的。

就假设我们的第一个例子：

coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

从amount(0)开始，amount(0)需要0枚硬币，amount(1)呢，我们取一枚硬币，amount(2)我们有两种选择，取一枚2元硬币，或者先取一枚硬币，剩下amount为一，再去取一枚，用算式来表达：amount(2) = amount(2 - 1) + 1，加上的1就是我取1的这一步操作，而减去的1则是为了取子问题中已经求出的解。

当然，比较一下大小，我们可以知道，取一枚两元硬币最方便。

接下来，我们考虑3枚的情况：我可以取一个两元和一个一元，或者三个一元，结果是2次和3次，自然取3次。

由此我们可以推出需要11枚的情况：

11 = 5 + 5 +1
11 = 5 + 2 + 2 + 1 + 1
...

情况是不是很多？不用慌张，在减去这步操作的数值后，调用的就是我们过去求得的子问题的解，也就是只要将三种情况比个大小就行了。

那么基本上，我们的状态转移方程也出来了。

d(i) = min{ d( i - coins[j] ) + 1}

d(i)表示amount = i时的情况，coins[j]则是在coins数组里取一个值。

那么很自然的，我们就能够做出我们的答案了：

var coinChange = function(coins, amount) {
    var length = coins.length,
        curr = length - 1,
        min = -1,
        arr = [],
        i = 1,
        j = length - 1;

    coins.sort(function(a, b) {
        return a - b;
    });

    arr[0] = 0;

    for (i = 1; i <= amount; i++) {
        min = -1;

        for (j = length - 1; j >= 0; j--) {
            if (coins[j] <= i) {
                curr = arr[i - coins[j]];

                if (min === -1 || min > curr && curr !== -1) {
                    min = curr;
                }
            }
        }

        if (min !== -1) {
            arr[i] = min + 1;
        }
        else {
            arr[i] = -1;
        }
    }

    return arr[amount];
};

分析过程就是这样，一步步由小及大就行了，剩下的刷到了新题再说吧，这次动规先入个门。

参考：

动态规划 - 维基百科

动态规划：从新手到专家