硬币换币逻辑

def coinChange(coins, amount):
    dp = [0] + [float('inf')] * amount
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # 输出: 3 (11 = 5 + 5 + 1)

def coinChange(coins, amount, coin_counts):
    dp = [[[float('inf')] * (coin_counts[c] + 1) for _ in range(amount + 1)] for _ in range(len(coins))]
    for i in range(len(coins)):
        dp[i][0][0] = 0
    for i in range(len(coins)):
        for j in range(amount + 1):
            for k in range(coin_counts[coins[i]] + 1):
                if j >= coins[i] * k:
                    dp[i][j][k] = min(dp[i][j][k], dp[i][j - coins[i] * k][0] + k)
                if i > 0:
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])
    return min(dp[-1][-1]) if min(dp[-1][-1]) != float('inf') else -1

coins = [1, 2, 5]
amount = 11
coin_counts = {1: 3, 2: 2, 5: 1}
print(coinChange(coins, amount, coin_counts))  # 输出: 3 (11 = 5 + 5 + 1)