Leetcode 322题 零钱兑换问题

题目及实例

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

1
2
3
4
5
示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
1
2
3
4
示例 2:

输入: coins = [2], amount = 3
输出: -1

这个题目乍一看像是贪心算法，但是贪心算法容易陷入局部最优，如coins=[1,2,7,10],全局最优解应为[7,7]，但是谈心会陷入局部最优解[2,2,10];

零钱问题曾经是我大二算法课考试的题目，一般会采用动态规划的解题思路,但是在leetcode的题解中看到了曾经我觉得性能可能会很差的回溯（+剪枝）的方法竟有很不错的性能，给了我很大的启发，所以下面我回把两个方法都介绍一边

动态规划

解析

动态规划其实是一个填表的过程，数组dp是一个长度为amount+1的数组（为什么要加1，因为钱数从0到amount有amount+1个数），其中第i个元素代表如果需要找i块钱需要的最少硬币数，这样一直算到最后，dp[amount]就是我们需要的答案。

那怎么保证从前往后的每一步都能得出当前的最少数目呢
首先我们把数组都初始化成一个最大值（这里用的是amount+1，因为数组中的元素不可能比amount大）
第一个元素当需要找的钱为0时，个数肯定是0
当找零数为i时,进行以下操作

1
2
3
4
for i:1 to coins.size() do
begin
    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
end

其实就是遍历coins列表，找到可以使当前数最小的值，dp[i]是原始值，代表不使用coins[j]这个硬币，dp[i - coins[j]] + 1代表使用这个硬币，计算里面的最小值，这样就保证了我每一个dp[i]都会是全局最优的情况，所以最后的结果也是全局最优

动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
     int coinChange(vector<int>& coins, int amount) {
         const int Max = amount + 1;
         int dp[Max];
         for(int i=1;i<Max;i++){
             dp[i]=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];

    }
};

回溯+剪枝

解析

这个算法只有回溯的话性能会很差，但是加上剪枝操作后会带来很多的性能提升，在提交中也取得了很好的结果，给了我很大的启发，这里要感谢leetcode上的Ikaruga的思路和代码
这个就是很简单的思想，我一个一个试，如果不成就回溯，如果成了就记录下当前的方案的结果，用一个变量记录全局的最优质的，每一个结果都会跟当前的最好的值比较，如果新得出的结果最好就更新全局的值

但是问题在于这样其实是很耗时的，如果我很早的就得出了最优的值那我后面还会做很多无谓的操作，这里剪枝的用处就出现了，下面的代码中用 k + count < ans 这个判断来进行了剪枝的操作，如果当前的数目已经没有成为最优解的可能性了，就不会再往下进行搜索。

这样最好情况下很快就能完成遍历，这其实就是一种贪心的思想，这也是提交结果很好的原因，因为很多情况下贪心算出的局部最优解就是全局最优。但是最坏情况下需要遍历所有的可能性，时间也会比动态规划长。

代码

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
class Solution {
public:
    void coinChange(vector<int>& coins, int amount, int c_index, int count, int& ans)
    {
        if (amount == 0)
        {
            ans = min(ans, count);
            return;
        }
        if (c_index == coins.size()) return;

        for (int k = amount / coins[c_index]; k >= 0 && k + count < ans; k--)
        {
            coinChange(coins, amount - k * coins[c_index], c_index + 1, count + k, ans);
        }
    }

    int coinChange(vector<int>& coins, int amount)
    {
        if (amount == 0) return 0;
        sort(coins.rbegin(), coins.rend());
        int ans = INT_MAX;
        coinChange(coins, amount, 0, 0, ans);
        return ans == INT_MAX ? -1 : ans;
    }

};