求解钱币兑换问题C++

在C++中解决钱币兑换问题是常见的计算机科学练习题，通常涉及到找零算法。假设有一个固定的钱币面额数组，比如1、5、10、25等，给定总金额，目标是找出最小组合数，使得这些面额能够组成这个金额。这个问题可以使用动态规划(Dynamic Programming)或回溯法(Brute Force)来解决。

**动态规划**做法通常会创建一个二维数组，其中每个元素表示前几个面额能组成的最大金额，通过比较当前面额加上前一状态的最优值和直接添加当前面额的新状态，找到最小组合。

**示例代码 (使用动态规划)：**

#include <vector>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<vector<int>> dp(amount + 1, vector<int>(coins.size(), -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-coins[j]] != -1)
                dp[i] = min(dp[i], dp[i-coins[j]] + 1);
        }
    }

    return dp[amount] == -1 ? -1 : dp[amount]; // 如果无法组成，则返回-1
}