用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。