动态规划问题(2) 之 由凑零钱认识最优子结构

由凑零钱问题认识 最优子结构

问题描述：

有k种⾯值的硬币，⾯值分别为 c1, c2...ck，每种硬 币的数量⽆限，再给⼀个总⾦额 amount，问你最少需要⼏枚硬币凑出这个⾦额，如果不可能凑出，算法返回 -1。

如：k = 3，⾯值分别为1，2，5，总⾦额amount = 11 。那么最少需要3枚硬币凑出，即11= 5 + 5 + 1。

1、暴力递归

这是一个动态规划的问题，其子问题必须互相独立，即选择每个金额的硬币都是相互独立的，

⽐如你想求  amount  = 11时的最少硬币数（原问题），如果你知道凑出 amount =10的最少硬币数（⼦问题），你只需要把⼦问题的答案加⼀（再选⼀枚⾯值为1的硬币） 就是原问题的答案，因为硬币的数量是没有限制的，⼦问题之间没有相互制约，是互相独⽴的。这个过程即符合最优子结构，每一个子问题都求得最少，最终的原问题就会是最少。

对于一个动态规划问题，就要思考如何列出正确的状态转移⽅程？

先确定状态，也就是原问题和⼦问题中变化的变量。由于硬币数量⽆限，所以唯⼀的状态就是⽬标⾦额amount。

然后确定 dp  函数的定义：当前的⽬标⾦额是 n ，⾄少需要dp(n) 个硬 币凑出该⾦额。

然后确定选择并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，⽆论当的⽬标⾦额是多少，选择就是从⾯额列表 coins 中选择⼀个硬币，然后⽬标⾦额就会减少。

最后再明确 base case，显然⽬标⾦额为0 时，所需硬币数量为 0；当⽬标⾦额⼩于0 时，⽆解，返回-1。

 此时，问题已经解决，接下来就是需要消除重叠子问题，给出递归树如下：

 2、带备忘录的递归

很显然备忘录⼤⼤减⼩了⼦问题数⽬，完全消除了⼦问题的冗余，所以⼦问题总数不会超过⾦额数n，即⼦问题数⽬为 O(n)。处理⼀个 ⼦问题的时间不变，仍是O(k)，所以总的时间复杂度是 O(kn)。

3、dp数组的迭代解法

使用自底向上的 dp table 来消除重叠子问题：

    dp[i] = x 表⽰，当⽬标⾦额为 i  时，⾄少需要 x 枚硬币。

int coinChange(vector<int>& coins, int amount)
{
    //	数组⼤⼩为amount+1，初始值也为amount+1
    vector<int>	dp(amount + 1,amount + 1);
    //	base case
    dp[0] = 0;
    for	(inti=0; i<dp.size(); i++)
    {
        //内层for在求所有⼦问题+1的最⼩值
        for(int coin : coins)
        {
            //	⼦问题⽆解，跳过
            if(i - coin < 0) continue;
            dp[i]= min(dp[i], 1+dp[i-coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}