动态编程的找零问题

由 发布于 pythoncoin-changedynamic-programming
 收藏

这是我的代码，用于打印一组硬币的总数和目标数量

def coin_change（硬币，金额）：

table=[0 for k in range(amount+1)]
table[0]=1
for coin in coins:
    for x in range(coin,amount+1):
        table[x] = table[x]+ table[x-coin]

    print(table)  

return table[amount]

我想知道是否有任何方法可以使用相同的动态编程解决方案来打印这些方式（借助内部构造表或任何其他方法）

评论
miste
miste

您可以跟踪每种面额的父母，然后按喜好打印。

def get_ways(amount, coins):
    table = [0 for k in range(amount+1)]
    table[0]=1
    parents = [[]  for _ in range(amount + 1)]
    for coin in coins:
        for x in range(coin,amount+1):
            table[x] = table[x]+ table[x-coin]
            parents[x].append(x - coin)
    print(parents)
    return table[amount]

print(get_ways(3, [1, 2, 3, 10]))

Parents数组会像这样打印

[[], [0], [1, 0], [2, 1, 0]]
点赞
评论