题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

plaintext
1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

具体见题目详解。

算法思路

对于这种问题，我最开始想的是贪心，因为你想让金币数量尽可能的少，还需要凑齐数额，就需要用尽可能大的金币面值。但这很显然进入了一个误区：全局最优并不代表局部最优。举个例子，对于 amount = 19, coins = [1, 6, 7]，如果从最大的硬币开始数，那么就是2个coin-7,5个coin-1，总共需要7个硬币；但是很显然，如果选取coin-6和coin-1，那么只需要4个就行了，最后这个想法肯定是没通过的，这里就不展示代码了。

后来我看了一下这个题目的标签，提示是动态规划，这样就很同意想清楚了，你要凑齐j元硬币，那么至少在[1~j]之间的某个数额（后面会讲具体的）你肯定能凑出来，否则这个j肯定是凑不出来的。

具体来说，我们记dp[i]为凑齐 i所需要的最小的金币数量，那么对于之前已经凑出来的i-coins[k], k= 0,1, ...n，我们只需要找到最小的dp[i - coins[k]] ，在此基础上加1（加上coins[k]）就能得到数额i。

因此，我写的代码如下：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 动态规划
        // dp[i]表示凑成i所需的最小硬币数量
        // dp[j] = min(dp[i] + dp[j-i]), 1 <= i <= j / 2
        if (amount == 0) {
            return 0;
        }
        vector <int> dp(amount + 1, 0);
        sort(coins.begin(), coins.end());
        if (coins[0] > amount) {
            return -1;
        }
        for (int i = 0; i < coins.size(); i++) {
            if (coins[i] > amount) {
                break;
            }
            dp[coins[i]] = 1; // 使用coins[i]即可表示自己
        }
        for (int i = 1; i <= amount; i++) {
            if (dp[i] == 1) {
                continue;
            }
            for (int coin : coins) {
                if (coin <= i && dp[i - coin]) {
                    dp[i] = dp[i] == 0 ? dp[i - coin] + 1 : min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == 0 ? -1 : dp[amount];
    }
};

总体思路是这样的，但是有点丑长了，效率也不咋地，但是和我同样的官方思路效率就非常快，可以看看他的代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

还有一种思路是广搜，也就是我们常说的暴力，纯暴力是百分百过不了的，需要加上记忆搜索，我这里就不写了，对这种解法不是很感兴趣，想看的点击此处自行查看。