Python Coin Change Dynamic Programming

Question

I am currently trying to implement dynamic programming in Python, but I don't know how to setup the backtracking portion so that it does not repeat permutations. For example, an input would be (6, [1,5]) and the expected output should be 2 because there are 2 possible ways to arrange 1 and 5 so that their sum is equivalent to 6. Those combinations are {1,1,1,1,1,1} and {1,5} but the way my program currently works, it accounts for the combinations displayed above and the combination {5,1}. This causes the output to be 3 which is not what I wanted. So my question is "How do I prevent from repeating permutations?". My current code is shown below.

    import collections as c

    class DynamicProgram(object):
        def __init__(self):
            self.fib_memo = {}
            # nested dictionary, collections.defaultdict works better than a regular nested dictionary
            self.coin_change_memo = c.defaultdict(dict)
            self.__dict__.update({x:k for x, k in locals().items() if x != 'self'})
        def coin_change(self, n, coin_array):
            # check cache
            if n in self.coin_change_memo:
                if len(coin_array) in self.coin_change_memo[n]:
            return [n][len(coin_array)]

            # base cases
            if n < 0: return 0
            elif n == 1 or n == 0: return 1

            result = 0
            i = 0

            # backtracking (the backbone of how this function works)
            while i <= n and i < len(coin_array):
                result += self.coin_change(n-coin_array[i], coin_array)
                i += 1

            # append to cache
            self.coin_change_memo[n][len(coin_array)] = result

            # return result
            return result

Possible duplicate of [Memoizing Coin Change](https://stackoverflow.com/questions/20742714/memoizing-coin-change) — Paul Hankin, Sep 17 '17 at 08:12

รยקคгรђשค · Answer 1 · 2017-09-22T07:12:36.870

1

Quick fix would be:

result += self.coin_change(n-coin_array[i], coin_array[i:]) # notice coin_array[i:] instead of coin_array

But you want to avoid this as each time you will be creating a new list.

Better fix would be:

Simply add a parameter lastUsedCoinIndex in the function. Then always use coins with index >= lastUsedCoinIndex from coin array. This will ensure that the solutions are distinct.

Also you will have to make changes in your memo state. You are presently storing sum n and size of array(size of array is not changing in your provided implementation unlike the quick fix I provided, so its of no use there!!) together as a state for memo. Now you will have n and lastUsedCoinIndex, together determining a memo state.

EDIT:

Your function would look like:

def coin_change(self,coin_array,n,lastUsedCoinIndex):

Here, the only variables changing will be n and lastUsedCoinIndex. So you can also modify your constructor such that it takes coin_array as input and then you will access the coin_array initialized by constructor through self.coin_array. Then the function would become simply:

def coin_change(self,n,lastUsedCoinIndex):

edited Sep 22 '17 at 07:12

answered Sep 17 '17 at 07:30

รยקคгรђשค

1,919
1
10
18

Would this include having an array of available coins implemented in the memo? – Matthew Anderson Sep 21 '17 at 19:46
I don't understand your above question clearly ... But the memo state would only contain `n` and `lastUsedCoinIndex` as variables which implicitly already provides information regarding coins available as given the entire array you can always know what coins are available for calculation. Does this clear your doubts? – รยקคгรђשค Sep 21 '17 at 20:56
I made some elaborations. See if it explains more clearly. – รยקคгรђשค Sep 21 '17 at 21:12
Sorry I wasn't clear. I meant to ask where the "lastUsedCoinIndex" parameter would b added to the function whether its an input or a variable initialized somewhere in the function. You're edit cleared up my confusion so thank you. – Matthew Anderson Sep 22 '17 at 13:20
Welcome, hope it helped. – รยקคгรђשค Sep 22 '17 at 13:53

score 1 · Accepted Answer · answered Sep 17 '17 at 08:31

One of the way of avoiding permutation is to use the numbers in "non-decreasing" order. By doing so you will never add answer for [5 1] because it is not in "non-decreasing" order.And [1 5] will be added as it is in "non-decreasing" order.

So the change in your code will be if you fix to use the ith number in sorted order than you will never ever use the number which is strictly lower than this.

The code change will be as described in Suparshva's answer with initial list of numbers sorted.

Python Coin Change Dynamic Programming

2 Answers2

Linked