Coin Change: verilen bozuk para türleriyle bir tutarı en az kaç parayla oluşturabilirsiniz?

Bu bir unbounded knapsack tipi dinamik programlama problemidir. dp[x] = x tutarı için gereken minimum para sayısı. Her tutar için son eklenen parayı deneriz: dp[x] = min(dp[x - c] + 1).

Neden greedy çalışmaz?

coins = [1, 3, 4], amount = 6 için greedy önce 4'ü alır: 4 + 1 + 1 = 3 para. Doğru cevap 3 + 3 = 2 paradır. Greedy yalnızca bazı "kanonik" para sistemlerinde (ör. 1, 5, 10, 25) doğrudur.

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 2, 5], 11))  # 3  (5 + 5 + 1)
print(coin_change([2], 3))         # -1
print(coin_change([1, 3, 4], 6))   # 2

Karmaşıklık

• Zaman: O(amount x len(coins))
• Bellek: O(amount)

İlgili varyasyon: Coin Change II

"Kaç farklı şekilde oluşturulur?" sorusunda döngü sırası önemlidir: dış döngü paralar, iç döngü tutarlar olursa kombinasyon sayılır (sıra önemsiz); tersi permütasyon sayar.

def change(amount, coins):
    ways = [1] + [0] * amount
    for c in coins:
        for x in range(c, amount + 1):
            ways[x] += ways[x - c]
    return ways[amount]