使用Python完成凑零钱问题（

在Python中，凑零钱问题通常是指经典的动态规划问题，也称为“改变零钞”问题。这个问题的目标是找出给定一些面额（如1元、5元、10元等），如何组合这些面额来支付恰好指定金额的最少张数。比如，你需要找零12元，可以有多种组合方式，如两枚5元加一枚1元，或者三枚2元。

解决这类问题的一般步骤是：

1. 定义状态：可以用一个二维数组dp[i][j]表示支付i元需要的最小张数，其中i是目标金额，j是当前拥有的最大面额。
2. 初始化：对于小额，可以直接使用大额面值，所以dp[0][j] = 0；对于大额，如果无法使用该面额，dp[i][j] = dp[i][j - 1] + 1。
3. 状态转移：遍历所有可能的面额，更新dp[i][j]，使其取值为当前面额加上使用其他面额dp[i - j][k]（k < j）所需的张数的最小值。
4. 返回结果：dp[target][max_denomination]即为目标金额的最小张数。

def min_coins(coin_values, target):
    dp = [[float('inf')] * (target + 1) for _ in range(len(coin_values) + 1)]
    dp[0][0] = 0

    for i in range(1, len(coin_values) + 1):
        for j in range(1, target + 1):
            if coin_values[i - 1] <= j:
                dp[i][j] = min(dp[i][j], dp[i - 1][j])
                dp[i][j] = min(dp[i][j], dp[i][j - coin_values[i - 1]] + 1)

    return dp[-1][-1]

# 示例
coin_values = [1, 5, 10]
target = 12
print(min_coins(coin_values, target))  # 输出：3