动态规划实现：返回凑成目标金额的最少硬币数组/Vector

要解决这个问题，我们可以在经典的「最少硬币数」动态规划解法基础上扩展——除了跟踪每个金额所需的最少硬币总数，还要记录每个金额达成时最后使用的硬币面额，最后通过回溯得到每种硬币的具体使用数量。下面是详细的实现思路和代码：

核心思路 #

1. 动态规划数组初始化：
   • 用dp数组存储每个金额（从0到目标金额）对应的最少硬币数，初始时dp[0] = 0（金额0不需要硬币），其余设为一个大于最大可能硬币数的值（比如amount + 1，因为最多用amount个1元硬币）。
   • 用prev_coin_index数组存储每个金额达成时，最后使用的硬币在输入数组中的索引，方便后续回溯统计数量。
2. 填充动态规划数组：遍历每个金额，尝试用每种硬币更新dp和prev_coin_index，确保每次都记录最少硬币数的选择。
3. 回溯统计硬币数量：从目标金额开始，通过prev_coin_index一步步回溯到金额0，统计每种硬币的使用次数。
4. 边界处理：如果目标金额为0，返回全0数组；如果无法凑出目标金额（即dp[amount]仍为初始的大数），返回空数组或自定义标记。

完整代码实现 #

#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<int> getCoinCounts(vector<int>& coins, int amount) {
    // 处理特殊情况：目标金额为0，返回全0数组
    if (amount == 0) {
        return vector<int>(coins.size(), 0);
    }
    // 处理无效输入：硬币为空或金额为负
    if (coins.empty() || amount < 0) {
        return {};
    }

    int n = coins.size();
    // dp[i]表示凑出金额i所需的最少硬币数
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    // 记录每个金额最后使用的硬币索引
    vector<int> prev_coin_index(amount + 1, -1);

    for (int i = 1; i <= amount; ++i) {
        for (int j = 0; j < n; ++j) {
            if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
                dp[i] = dp[i - coins[j]] + 1;
                prev_coin_index[i] = j;
            }
        }
    }

    // 无法凑出目标金额的情况
    if (dp[amount] == amount + 1) {
        return {};
    }

    // 回溯统计每种硬币的数量
    vector<int> counts(n, 0);
    int remaining = amount;
    while (remaining > 0) {
        int idx = prev_coin_index[remaining];
        counts[idx]++;
        remaining -= coins[idx];
    }

    return counts;
}

// 测试示例
#include <iostream>
int main() {
    vector<int> coins = {1, 2, 5, 10};
    int target = 12;
    vector<int> result = getCoinCounts(coins, target);
    
    cout << "各面额硬币使用数量：";
    for (int num : result) {
        cout << num << " ";
    }
    // 输出：0 1 0 1 （对应1元0个，2元1个，5元0个，10元1个）
    return 0;
}

代码解释 #

• 特殊情况处理：先快速处理金额为0、无效输入的场景，避免后续逻辑出错。
• 动态规划填充：对于每个金额i，遍历所有硬币，如果当前硬币面额不超过i，且用该硬币凑出i的硬币数更少，就更新dp[i]和对应的硬币索引。
• 回溯统计：从目标金额反向推导，每次找到最后使用的硬币，累加计数并减去该硬币面额，直到剩余金额为0，最终得到每种硬币的使用数量。
• 测试示例：针对题目中的例子，运行后会输出0 1 0 1，正好符合最少硬币数（1个10元+1个2元，共2枚）的要求。

内容的提问来源于stack exchange，提问作者J.Einhorn