下面我将以通俗易懂的方式，为你详细讲解硬币找零问题的C++实现。这个问题非常适合中小学生入门动态规划思想，我会用简单的语言和丰富的例子帮助你理解。

硬币找零问题介绍

硬币找零问题是一个经典的算法问题：假设你是一个收银员，需要给顾客找零一定金额（比如11元），你有不同面值的硬币（比如1元、5元、10元），如何用最少的硬币数量完成找零？

解题思路

我们可以使用动态规划的思想来解决这个问题。动态规划的核心是将复杂问题分解为简单子问题，并保存子问题的解避免重复计算。

对于硬币找零问题，我们可以定义一个数组dp，其中dp[i]表示凑出金额i所需的最少硬币数量。然后逐步计算dp[0]到dp[目标金额]的值。

C++代码实现

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

int coinChange(vector<int>& coins, int amount) {
    // 创建一个数组dp，dp[i]表示凑出金额i需要的最少硬币数量
    // 初始值设为amount+1，因为最多需要amount个1元硬币，amount+1作为无穷大使用
    vector<int> dp(amount + 1, amount + 1);
    
    // 凑出金额0需要0个硬币
    dp[0] = 0;
    
    // 从金额1开始逐步计算到目标金额amount
    for (int i = 1; i <= amount; i++) {
        // 对于每个金额i，遍历所有可能的硬币面值
        for (int coin : coins) {
            // 如果当前硬币面值不大于金额i，说明可以使用这个硬币
            if (coin <= i) {
                // 更新dp[i]的值，取当前值和使用当前硬币后的更小值
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    // 如果最终dp[amount]仍然是amount+1，说明无法凑出该金额，返回-1
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    // 可用的硬币面值
    vector<int> coins = {1, 5, 10};
    // 要找零的金额
    int amount = 11;
    
    // 调用coinChange函数计算最少硬币数量
    int result = coinChange(coins, amount);
    
    // 输出结果
    if (result != -1) {
        cout << "凑出 " << amount << " 元最少需要 " << result << " 个硬币。" << endl;
    } else {
        cout << "无法凑出 " << amount << " 元。" << endl;
    }
    
    return 0;
}

代码解释

1. 初始化数组dp：dp[i]初始化为amount+1，这是一个不可能的硬币数量，用于表示初始状态。dp[0]设为0，因为凑出金额0不需要任何硬币。

2. 遍历金额：从1到目标金额amount，依次计算每个金额所需的最少硬币数量。

3. 遍历硬币面值：对于每个金额i，检查每个硬币面值是否可以使用。如果硬币面值coin小于等于i，则可以使用这个硬币。

4. 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)。这个方程的意思是，使用当前硬币coin后，凑出金额i的最少硬币数量等于凑出金额i - coin的最少硬币数量加1。

5. 结果判断：如果最终dp[amount]仍然是amount+1，说明无法凑出该金额，返回-1。

举个例子

假设我们有硬币面值1元、5元、10元，要凑出11元。

• dp[0] = 0（初始条件）
• dp[1] = 1（使用1个1元硬币）
• dp[2] = 2（使用2个1元硬币）
• dp[3] = 3（使用3个1元硬币）
• dp[4] = 4（使用4个1元硬币）
• dp[5] = 1（使用1个5元硬币，比5个1元硬币更优）
• dp[6] = 2（使用1个5元+1个1元）
• dp[7] = 3（使用1个5元+2个1元）
• dp[8] = 4（使用1个5元+3个1元）
• dp[9] = 5（使用1个5元+4个1元）
• dp[10] = 1（使用1个10元硬币）
• dp[11] = 2（使用1个10元+1个1元）

这样，我们就用最少的硬币数量（2个）凑出了11元。

这个算法的时间复杂度是O(amount * coins.size())，空间复杂度是O(amount)。通过这种方法，我们可以高效地解决硬币找零问题。