硬币面值组合问题c++

好的，硬币面值组合问题是一个经典的动态规划问题。假设有一堆不同面值的硬币，每种面值的硬币数量无限，现在需要用这些硬币凑出一个给定的金额，问有多少种不同的凑法？

我们可以定义一个一维数组 dp，其中 dp[i] 表示凑出金额 i 的不同组合数。对于每个硬币面值 j，如果 j <= i，则 dp[i] += dp[i-j]。

下面是 C++ 的代码实现：

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i-coin];
        }
    }
    return dp[amount];
}

其中 coins 是硬币面值数组，amount 是需要凑出的金额。

相关问题

c++ dag动态规划 硬币问题

在C++中，可以使用动态规划解决硬币问题。下面是一个示例代码：

#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`数组，最终得到最小硬币数量。

用C++暴力求解硬币找钱问题

硬币找钱问题可以使用贪心算法求解，但是如果硬币面值不是固定的，或者需要凑出的金额超过了硬币面值的总和，贪心算法就会失效。这时候可以使用动态规划算法来解决问题。

具体来说，我们可以定义一个一维数组 dp，其中 dp[i] 表示凑出金额 i 需要的最少硬币数。初始化时，dp[0]=0，其余元素全部赋值为无穷大，表示当前金额无法凑出。然后我们依次枚举硬币面值，对于每个面值 j，更新 dp 数组中所有满足 i>=j 的元素 dp[i]，使其取值为 dp[i-j]+1 和 dp[i] 中的较小值。最终得到的 dp[amount] 就是凑出金额 amount 所需的最少硬币数。

以下是使用 C++ 编写的代码实现：

#include <iostream>
#include <cstring>
#include <climits>

using namespace std;

const int MAXN = 1e5 + 5;

int n; // 硬币面值种类数
int a[MAXN]; // 硬币面值数组
int dp[MAXN]; // dp 数组

int main() {
    int amount;
    cin >> amount >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    memset(dp, 0x3f, sizeof(dp)); // 初始化为无穷大
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= amount; j++) {
            dp[j] = min(dp[j], dp[j-a[i]]+1);
        }
    }
    if (dp[amount] == INT_MAX) { // 无法凑出所需金额
        cout << -1 << endl;
    } else {
        cout << dp[amount] << endl;
    }
    return 0;
}

输入格式为：

amount n
a1 a2 ... an

其中 amount 表示需要凑出的金额，n 表示硬币面值种类数，a1 到 an 表示每种硬币的面值。输出格式为凑出所需金额的最少硬币数，如果无法凑出则输出 -1。