# 找零問題
def coinChange(coins, amount):
    """
    :type coins: List[int]
    :type amount: int
    :return: num of used coins  
    """
    dp = [amount + 1 for _ in range(amount + 1)]
    used = [0 for _ in range(amount + 1)]

    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            if dp[i] >  dp[i - coin] + 1:
                dp[i] = dp[i - coin] + 1
                used[i] = coin
    return used, dp[amount] if dp[amount] < amount + 1 else -1

def used_detail(coins, used, amount):
    dicts = {i: 0 for i in coins}
    while amount > 0:
        dicts[used[amount]] += 1
        amount -= used[amount]
    return dicts

coins = [1,2,5,10]
amount = 63
used, num = coinChange(coins, amount)
d = used_detail(coins, used, 63)

print('number of coins: ', num)
print(d)