322.零钱兑换

2020-05-19

题目

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

示例 1:
1
2
3
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:
1
2
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题与完全平方数一题完全一样。对于每一个给定的总数 $amount$ ，每选一枚硬币时，有 $n$ 种选择， $n$ 为硬币面值种数，此时，对于 $amount$ ，我们有了以它为根节点的一棵决策树，每个结点的值为最小硬币数。与完全平方数一样，我们有了状态转移方程之后，自上而下地递归、自下而上的动态规划，都可以解决问题，这里我们依然用动态规划。

动态规划

这里取状态为输入为 $i$ 时最小硬币数量。

注意：如果对于一个输入，没有可选选择，那么应该返回-1。

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

时间复杂度 $O(coins.size()*amount)$
空间复杂度 $O(amount)$

贪心+DFS

正如完全平方数中我本来想要实现的那样，使用贪心算法优先取面值更大的硬币。然而这样计算的bug在于不一定求到全局最优解。精选题解代码如下：

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;
}

作者：ikaruga
链接：https://leetcode-cn.com/problems/coin-change/solution/322-by-ikaruga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。