c++ dag动态规划 硬币问题
时间: 2023-12-27 09:25:43 浏览: 31
在C++中,可以使用动态规划解决硬币问题。下面是一个示例代码:
```cpp
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
int main() {
int n;
cin >> n;
vector<int> coins(n);
for (int i = 0; i < n; i++) {
cin >> coins[i];
}
int amount;
cin >> amount;
int minCoins = coinChange(coins, amount);
cout << "Minimum number of coins required: " << minCoins << endl;
return 0;
}
```
这段代码使用了一个一维数组`dp`来保存每个金额所需的最小硬币数量。通过遍历硬币面值和金额,不断更新`dp`数组,最终得到最小硬币数量。