LeetCode322. Coin Change（动态规划）

LeetCode322. Coin Change（动态规划）

• Medium
• Accepted：178,923
• Submissions：601,974

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.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

链接

https://leetcode.com/problems/coin-change

题意

给定一些不同面额的硬币和一个总金额，求使用这些硬币凑成总金额的最少数量。没法凑成就返回-1。

题解

非常经典的一道题，有一个非常好的解答：什么是动态规划？动态规划的意义是什么？ - 阮行止的回答 - 知乎，我在这里截取其中一部分。

　　先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。

　　依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。

　　这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。

　　但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：
　　15=1×11+4×1 （贪心策略使用了5张钞票）
　　15=3×5 （正确的策略，只用3张钞票）
　　为什么会这样呢？贪心策略错在了哪里？

　　鼠目寸光。
　　刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。
　　在这里我们发现，贪心是一种只考虑眼前情况的策略。

　　那么，现在我们怎样才能避免鼠目寸光呢？

　　如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。

　　重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。

　　那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？
　　明显$cost=f(4)+1=4+1=5$ ，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。
　　依次类推，马上可以知道：如果我们用5来凑出15，cost就是$f(10) + 1 = 2 + 1 = 3$。

　　那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个！

• 取11：$cost=f(4)+1=4+1=5​$
• 取5： $cost=f(10)+1=2+1=3​$
• 取1： $cost=f(14)+1=4+1=5$

　　显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策！

　　这给了我们一个至关重要的启示—— f(n)只与 f(n-1),f(n-5),f(n-11)相关；更确切地说：

$$f(n)=min\{f(n-1),f(n-5),f(n-11)\}+1​$$

　　这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。

看懂了这个回答，我们这道题也是一样的，$dp[mounts] = min\{dp[mounts-coins[j]]\} + 1$，注意一下不能凑出时的处理，如果dp[amount] == amount + 1（一开始设置的初值），那么就说明没法凑成。

时间复杂度$O(n*amount)$，空间复杂度$O(n)$。

代码

• Runtime: 44 ms, faster than 85.61% of C++ online submissions for Coin Change.
• Memory Usage: 12.6 MB, less than 90.13% of C++ online submissions for Coin Change.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector <int> dp(amount + 1, 0);
        for (int i = 1; i <= amount; ++i)
        {
            int cost = amount + 1;
            for (int j = 0; j < n; ++j)
                if (i >= coins[j])
                    cost = min(cost, dp[i - coins[j]] + 1);
            dp[i] = cost;
        }
        if (dp[amount] == amount + 1)
            return -1;
        return dp[amount];
    }
};

The end.
2019年4月9日 星期二