C++代码杂货店老板的小抽屉里有一堆不同面值的硬币，在给顾客找零时他习惯去凑成总金额所需的最少的硬币个数。你能不能写个程序帮他实现，若凑不出则返回-1。 【样例】 输入： coins：1,2,5 amount：11 输出： 3 11=5+5+1

思路：动态规划

定义状态：dp[i] 表示凑成金额 i 所需的最少硬币个数。

状态转移方程：dp[i] = min(dp[i], dp[i - coins[j]] + 1)，其中 coins[j] 表示第 j 个硬币的面值。

初始状态：dp[0] = 0，表示凑成金额为 0 不需要硬币。

最终答案：dp[amount]，表示凑成总金额所需的最少硬币个数。

如果 dp[amount] 仍为初始值，说明无法凑出总金额，返回 -1。

时间复杂度：O(amount*n)，其中 n 表示硬币的个数。

代码实现：

int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (i >= coins[j]) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}

相关问题

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

### 回答1：
这道题目要求编写一个函数来计算能够凑成总金额最小的硬币数量，给出硬币面额不同和总金额amount。编写的函数应该返回最少硬币个数，如果没有任何一种硬币组合能够凑成总金额，则返回-1。可以使用C++来实现该函数。

### 回答2：
本题是一道经典的动态规划问题，我们可以通过构建一个二维数组来解决该问题。具体步骤如下：

1.初始化

我们定义一个二维数组dp[i][j]，其中i表示硬币的种类数量，j表示总金额。dp[i][j]表示用前i个硬币凑成总金额为j所需的最小硬币数。我们将dp数组中所有的元素初始化为0。

2.状态转移方程

我们需要寻找状态转移方程，以便在dp数组中标记出每一个金额所需的最小硬币数。假设当前遍历的硬币面值为coin，则状态转移方程为：

dp[i][j] = min(dp[i-1][j], dp[i][j-coin]+1)

其中，dp[i-1][j]表示不使用当前硬币所需要的最小硬币数， dp[i][j-coin]+1 表示使用当前硬币所需要的硬币数，当然钱币总额不能小于当前硬币面额。

3.边界处理

对于dp数组边界的处理，我们需要将dp数组的第一列设置为0，因为总金额为0时，所有硬币数都是0；当硬币数量为0时，没有硬币可以使用，所以除了dp[0][0]等于0以外，其他值都为正无穷。

4.返回结果

最后，我们返回dp[i][j]即可，如果dp[coins.length][amount]的值大于amount，说明无法组成该金额，返回-1；反之，返回dp[coins.length][amount]。

最少硬币数的Java代码如下：

public int coinChange(int[] coins, int amount) {
int[][] dp = new int[coins.length+1][amount+1];
for(int i = 0; i <= coins.length; i++) {
dp[i][0] = 0;
}
for(int j = 1; j <= amount; j++) {
dp[0][j] = Integer.MAX_VALUE;
}
for(int i = 1; i <= coins.length; i++) {
for(int j = 1; j <= amount; j++) {
if(j < coins[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-coins[i-1]]+1);
}
}
}
return dp[coins.length][amount] > amount ? -1 : dp[coins.length][amount];
}

### 回答3：
这道题如果使用暴力枚举每一种硬币组合的话，时间复杂度将会非常高，因此需要使用动态规划来解决问题。

例如，我们假设要凑出总金额amount，coins的面值为[1,2,5]。我们可以定义一个数组dp，其中dp[i]表示凑出金额i所需的最少硬币个数。

那么我们怎样求出dp[i]呢？我们可以枚举每一个硬币的面值，如果硬币的面值小于等于i，那么凑出金额i所需的最少硬币个数就是dp[i-coins[j]]+1，其中j表示第j个硬币的面值与i相加等于总金额。

例如，当i=5时，我们可以选择使用面值为1的硬币，此时凑出金额5所需的最少硬币个数就是dp[4]+1，因为我们在凑出金额4的基础上，使用一个面值为1的硬币即可凑出金额5。

因此，我们可以使用如下的状态转移方程：

dp[i] = min(dp[i-coins[j]]+1)

其中j满足coins[j] <= i

最终，如果dp[amount]==INF，说明无法凑出总金额，此时返回-1即可。

以下是C代码实现：

#define INF 0x3f3f3f3f

int coinChange(int* coins, int coinsSize, int amount){
int dp[10001], i, j;
memset(dp, INF, sizeof(dp));
dp[0] = 0;
for (i = 1; i <= amount; i++) {
for (j = 0; j < coinsSize; j++) {
if (coins[j] <= i && dp[i-coins[j]] != INF) {
dp[i] = fmin(dp[i], dp[i-coins[j]]+1);
}
}
}
if (dp[amount] == INF) {
return -1;
}
return dp[amount];
}

假设现在有面值为1元，3元，5元的硬币若干枚，如何用最少硬币数凑够需要的金额？现输入一个表示需要的金额，要求输出一个整数表示最少的硬币数。用c＋＋代码做出来

好的，以下是使用贪心算法解决这个问题的C++代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    // 输入需要凑够的金额
    int amount;
    cin >> amount;

    // 定义三种硬币的面值
    vector<int> coins = {5, 3, 1};

    // 定义计数器和余额
    int count = 0;
    int balance = amount;

    // 贪心算法
    for (int i = 0; i < 3; i++) {
        while (balance >= coins[i]) {
            balance -= coins[i];
            count++;
        }
    }

    // 输出结果
    cout << count << endl;

    return 0;
}

首先，我们定义三种硬币的面值，然后定义计数器count和余额balance，初始值分别为0和需要凑够的金额amount。接下来，我们从面值最大的硬币开始，尽可能多地使用该硬币凑出余额，直到余额小于该硬币面值为止。然后，再使用面值次大的硬币，以此类推，直到余额为0为止。最后，输出计数器count即可。

需要注意的是，贪心算法并不一定能够得到最优解。在这个问题中，当需要凑够的金额为8时，贪心算法会先选一个5元硬币，再选一个3元硬币，共需两枚硬币。但实际上，最优解是使用三个1元硬币，共需三枚硬币。因此，对于一些特殊情况，贪心算法并不一定是最好的选择。