c++怎么解决最少钞票问题

在C++中，解决“最少钞票”问题通常涉及动态规划算法，也称为找零钱问题。这个问题的目标是最小化给出一定金额时所需的最小面额货币组合。例如，给定有5元、10元和20元的硬币，如何用最少的硬币凑出100元。

下面是一个简单的步骤：

1. 定义一个二维数组dp，其中`dp[i]`表示找到总金额i所需的最小硬币数。初始化所有dp值为无限大（如int类型的max_value），除了dp[0]设置为0，因为不需要任何硬币来凑零元。

2. 遍历从1到目标金额的所有整数i。对于每个i，检查是否有可用的硬币j（如5、10、20元等），然后更新dp[i]，如果加上当前硬币的数量小于等于dp[i-j]+1（即当前方案加一个j元硬币比上一个更优），则更新dp[i]为这个更小的结果。

3. 最终，dp[target_amount]就是所需的最小硬币数。遍历dp数组，找出能到达target_amount的那个状态对应的最小硬币数。

#include <iostream>
#include <vector>
using namespace std;

int minCoins(int coins[], int m, int target) {
    vector<int> dp(target + 1, INT_MAX);
    dp[0] = 0;
    
    for (int i = 1; i <= target; ++i) {
        for (int j = 0; j < m && coins[j] <= i; ++j) {
            if (dp[i-coins[j]] != INT_MAX)
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        }
    }

    return dp[target] == INT_MAX ? -1 : dp[target]; // 返回-1表示无法凑够目标金额
}

// 测试示例
int main() {
    int coins[] = {5, 10, 20};
    int m = sizeof(coins)/sizeof(coins[0]);
    int target = 100;
    cout << "Minimum number of coins: " << minCoins(coins, m, target) << endl;
    return 0;
}