每日一题-8

题目描述

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

示例 1:

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

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

解题思路

1.由于面额的不确定，所以简单的贪心可能得不到最优解。（例如硬币数为1,7,10，amount为15时。贪心得到的解是 15=10+1+1+1+1。而最优解应该为7+7+1,在第二种方法中，利用dfs可以解决这个问题。）
这题可以使用动态规划的方法。
首先设置一个dp数组，dp[i]代表总金额为i时，最少所需的硬币数。
动态规划其实也是一种暴力的算法，只是它存储了以前已经计算的值，避免了重复计算和一些不合理的计算。
已示例1为例子，conins=[1,2,5]， amount=11
我们从后往前推，可以推出
dp[amount] = min(dp[amount-1],dp[amount-2],dp[amount-5])+1
因为每次只能拿1,2,5三种硬币，那么在凑齐amount的前一步，一定只能是从
dp[amount-1],dp[amount-2],dp[amount-5]这三种情况而来。我们选择其中最小的情况，最后一步再拿这枚硬币，所得dp[amount]即为最优解。
状态转移方程： dp[x] = min(dp[x], dp[x-coin]+1)

2.虽然简单的贪心不行，但是贪心+dfs确可以解决这个问题。下面是别人c++的dfs+贪心代码。

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        #动态规划
        dp = [float("inf")]*(amount+1)
        dp[0] = 0

        for coin in coins:
            for x in range(coin, amount+1):
                dp[x] = min(dp[x], dp[x-coin]+1)

        #两种循环都可以

        for x in range(1, amount+1):
            for coin in coins:
                if x-coin<0:
                    continue
                dp[x] = min(dp[x], dp[x-coin]+1)

        return -1 if dp[amount]==float("inf") else dp[amount]