Dynamic programming solution inappropriate for change-making problem?

jbuddy_13 0
Viewed 42

I'm curious why my approach to the change-making problem isn't succeeding. The logic makes sense to me, so I'm not sure where the failure is.

def count_change(denoms, denoms_length, amount):
    """
    Finds the number of ways that the given number of cents can be represented.
    :param denoms: Values of the coins available
    :param denoms_length: Number of denoms
    :param amount: Given cent
    :return: The number of ways that the given number of cents can be represented.
    """

    # Write your code here!
    return helper(denoms, amount)

def helper(denoms, amount, i=0):
    if amount == 0:
        return 1
    elif i >= len(denoms):
        return 0
    else:
        count = 0
        coin = denoms[i]
        if coin < amount:
            mult = amount // coin
            for m in range(1, mult+1):
                count += helper(denoms, amount - (coin*m), i+1)
        else:
            count += helper(denoms, amount, i+1)
        
        return count

count_change([25, 10, 5, 1], 4, 30)
>>> 1 #should be 18

This problem is behind a paywall so I cannot link. The part that is most confusing to me is when a coin has several multiples that are less than the amount. This is the spirit behind the for loop in the else clause.

What am I doing wrong here?

dynamic-programming python
2 Answers
def count_change(denoms, denoms_length, amount):
    return helper(denoms, amount)

def helper(denoms, amount, i=0):
    if amount == 0:
        return 1
    elif i >= len(denoms):
        return 0
    else:
        count = 0
        coin = denoms[i]

        mult = amount // coin
        for m in range(0, mult+1):
            count += helper(denoms, amount - (coin*m), i+1)
        
        return count

count_change([25, 10, 5, 1], 4, 30)

We've changed a few things. We should ask ourselves how the code is supposed to work. It recursively works with each coin, deciding how many we want to use in the answer.

We could use any amount from 0 to the biggest that fits (you called it mult).
Please note that the original code would not use the coin if it is precisely equal to amount, due to if coin < amount:. We could change it to if coin <= amount: for now.

Next, you should notice that we don't try to use 0 coins. That case is only governed by the nested else. That's wrong - not using a coin is a viable option! So we should take the second part out of the else clause. Now we can realize that expanding the for loop with the starting point of 0 accomplishes the same thing. Now the code works.

Now, we should deal with the idea of dynamic programming. This solution uses the same idea as dynamic programming would, but it does so recursively. Every representation counted comes from a return 1. This results in a LOT of computation. To combat this and make it a dynamic programming solution the easiest, we can use a technique called memoization.

def count_change(denoms, denoms_length, amount):
    memory = {}

    def helper(amount, i=0):
        if amount == 0:
            return 1

        if i >= len(denoms):
            return 0

        if (amount, i) not in memory:
            count = 0
            coin = denoms[i]

            mult = amount // coin
            for m in range(0, mult+1):
                count += helper(amount - (coin*m), i+1)

            memory[(amount, i)] = count

        return memory[(amount, i)]

    return helper(amount)

We've added a dict memory that ensures that each pair of (amount, i) is only processed once, bringing out time complexity way down. Also, removed denoms from helper arguments, because it's constant throughout the process.

A more classic dynamic programming approach would instead use an amount x denoms_length size array and populate it with the answers to all options. If you do that carefully, you can even bring the complexity down to a cool O(amount * denoms_length), but that's a story for another day.

Jan Kanty Milczek0

Just cannot help to attempt this true DP solution to demo how easier to translate the previous memo version to a DP one (even prev. post has did excellent job explaining all logic ...)

It uses 1D ways to store all possible results and finally return the last one.



def count_changes(coins: List[int], amt: int) -> int:
    coins.sort()          # ascending order to ease later processing 
    ways = [1] + [0] * amt

    # Time: O(amt * coins)
    for coin in coins:
        for x in range(coin, amt + 1):
            ways[x] += ways[x - coin]
            #print(ways)
            
    return ways[amt]

if __name__ == '__main__':
    coins = [1, 5, 10, 25]

    print(count_changes(coins, 22))    #  9
    print(count_changes(coins, 30))    # 18
Daniel Hao0
Related