LeetCode 322. Coin Change

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:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.

思路

动态规划的问题，不过如果倒着做的话，似乎会超时…
所以考虑往前递推的情况，即当前要解决X元的找零问题的最佳解法且已知<X时的解法，手头有一堆面值为coins[i]的硬币的时候，对于每种可用的硬币我们要做的选择是：

• 尝试使用coin[i]，即当前的最优结果=(X-coins[i])元时的最优结果+1，这个1就是用了coins[i]这个硬币；
• 保持现有结果不变

这两个方法当然是取最好的存下来了。

代码

class Solution {
public:
    int MAX_NUM = 65535;
    int coinChange(vector<int>& coins, int amount) {
        vector<int> solutions(amount+1, MAX_NUM); //0~amount，共amount+1个
        solutions[0] = 0;
        int coinSz = coins.size();
        for(int i=1; i<=amount; i++){
            for(int c=0; c<coinSz; c++){
                //得到当前的amount，要么就是用原有的结果，要么就是使用amount[i-coin] + 1个当前面值的
                if(coins[c] <= i){
                    solutions[i] = min(solutions[i], 1 + solutions[i-coins[c]]);
                }
            }
        }
        if(solutions[amount] == MAX_NUM)
            return -1;
        return solutions[amount];
    }
};