Debug coin change Dynamic Programming

1
votes

My coin change dynamic programming implementation is failing for some of the test cases, and I am having a hard time figuring out why:

Problem Statement: Given an amount and a list of coins, find the minimum number of coins required to make that amount.

Ex:
Target Amount: 63
Coin List: [1, 5, 10, 21, 25]
Output: [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()

Trinket: https://trinket.io/python/43fcff035e

1
recursiondynamic-programming

1 Answers

2
votes

You're corrupting the variable, changes, by appending to it during a loop. Try this:

Replace these two lines:

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

With:

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