c++最少 硬币数的找零
时间: 2024-01-21 12:18:13 浏览: 28
这是一个经典的动态规划问题。假设有一个长度为 n 的数组 coins,表示所有可用的硬币面额,还有一个整数 amount,表示需要找零的总金额。我们需要计算出最少需要多少个硬币才能凑出总金额。
我们可以用一个长度为 amount+1 的数组 dp 来记录每个金额所需的最少硬币数。初始时,将 dp 数组全部赋值为 amount+1,因为无论如何,最多只能用 amount 个硬币凑出总金额,超过这个数量就没有意义了。
然后,我们依次对每个金额进行遍历,对于每个金额 i,我们从所有可用的硬币面额中选择一个硬币 j,如果 j 小于等于 i,说明这个硬币可以用来凑出金额 i。我们可以用一个状态转移方程来更新 dp[i] 的值:
dp[i] = min(dp[i], dp[i-j]+1)
其中 dp[i-j]+1 表示用一个硬币 j 凑出金额 i-j,并且需要再加上一个硬币 j 才能凑出金额 i。我们需要在所有可用的硬币面额中找到一个能够凑出金额 i 的最小值,这就是 dp[i] 的最终值。
最后,如果 dp[amount] 的值仍然是 amount+1,说明无法用给定的硬币凑出总金额,返回 -1;否则返回 dp[amount]。
下面是 C++ 的代码实现:
```cpp
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 (coins[j] <= i) {
dp[i] = min(dp[i], dp[i-coins[j]]+1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
```