python - 动态规划的硬币找零问题

Question

这是我关于硬币更换问题的代码，用于打印一组硬币的方式总数和目标数量

def coin_change(coins,amount):
    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]

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

例如，如果一组硬币是 [1,3,5] 并且目标数量是 6，那么总共有 4 种可能的方式。[[1,1,1,1,1,1,],[1,1,1,3],[3,3],[1,5]] 我想要这种方式的列表作为输出。

标签： pythondynamic-programmingcoin-change

Answer 1

根据您的要求编辑的答案：

def combine(parent, me):
    if len(parent) == 0:
        return [[me]]
    new_list = []
    for entry in parent:
        new_list.append(entry + [me])
    return new_list


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


print(get_ways(6, [1, 3, 5]))

输出：

[[1, 1, 1, 1, 1, 1], [1, 1, 1, 3], [3, 3], [1, 5]]
4