调试硬币变化动态编程

Question

我的硬币兑换动态编程实现在一些测试用例中失败，我很难找出原因：

问题陈述：给定一个数量和一个硬币列表，找出制造该数量所需的最小硬币数量。

例如：
目标金额：63
硬币列表：[1,5,10,21,25]
输出：[21,21,21]

def coin_change(change_list, amount, tried):
    if amount <= 0:
        return []
    if amount in change_list:
        return [amount]
    if amount in tried:
        return tried[amount]
    coin_count = []
    for change in change_list:
        if change < amount:
            changes = coin_change(change_list, amount-change, tried)
            changes.append(change)
            coin_count.append(changes)
    min_changes = coin_count[0][:]
    for x in coin_count[1:]:
        if len(min_changes) >= len(x):
            min_changes = x[:]
    tried[amount] = min_changes[:]
    return min_changes


def main():
    for amount in range(64):
        changes = coin_change([1, 5, 10, 21, 25], amount, {})
        if sum(changes) != amount:
            print "WRONG: Change for %d is: %r" % (amount, changes)
        else:
            # print "Change for %d is: %r" % (amount, changes)
            pass


if __name__ == "__main__":
    main()

小装饰品：https://trinket.io/python/43fcff035e

Answer 1

通过在循环过程中追加变量，changes，您正在破坏该变量。试试这个：

替换这两行：

changes.append(change)
coin_count.append(changes)

与：

_changes = changes[:] + [change]
coin_count.append(_changes)