pythondynamic-programmingtopdown

Issue in the top down approach to the Coin Change (Similar to the 0-1 backpack problem)

I am now working on the Leetcode 322. Coin Change, the question is as following:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3 Output: -1

Example 3:

Input: coins = [1], amount = 0 Output: 0

Example 4:

Input: coins = [1], amount = 1 Output: 1

Example 5:

Input: coins = [1], amount = 2 Output: 2

I tried to solve it via the top-down DP with memorization. I set a parameter in the helper function to remember the count.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        c = set(coins)
        dp = [0] * (amount + 1)

        def helper(a, count):
            if a == 0:
                return count
            # if a in c:
            #    return 1 + count
            if dp[a] != 0:
                return dp[a]
            res = math.inf
            for coin in c:
                if a - coin >= 0 and helper(a-coin, count+1) != -1:  
                    res = min(res, helper(a-coin, count+1))
            dp[a] = res if res < math.inf else -1
            return dp[a]

        return helper(amount, 0)

But it won't pass the case as:

[1,2,5] 100

The result supposes to be 20, but I got 92.

I tried to figure it out the whole afternoon, but not sure where I did wrong. I hope you can give me some suggestion where I went wrong.

Thanks in advance for your help.

Solution

  • !!! THIS IS A COMPLETE SOLUTION !!!

    Ok, so here is my solution to this problem (idea explained below):

    def solve(lst, amount):
    lst = sorted(lst, key=lambda x: x, reverse=True)
    cases = []
    for seq in [lst[i:] for i in range(len(lst))]:
        current_amount = 0
        count = 0
        for item in seq:
            while True:
                if current_amount + item == amount:
                    count += 1
                    current_amount += item
                    break
                elif current_amount + item > amount:
                    break
                elif current_amount < amount:
                    count += 1
                    current_amount += item
            if current_amount == amount:
                break

        if current_amount == amount:
            cases.append(count)

    if cases:
        return min(cases)
    return -1


print(solve([1, 2, 5], 100))
print(solve([1, 5, 7, 9], 12))

# 20
# 2

    Explanation:

    !!! MAIN IDEA
    First You have to start with the largest number in the list because it takes the least amount of additions to come the closest or completely become the final amount. !!!

    EDIT As suggested by @nitinkumarp in comments, previous version (can check edits but why?) failed in some cases as mentioned in the comment, a workaround for that issue is to check all sequences in order, still using the greedy approach but slicing the original list shorter and shorter so that it can also check the correct solution which is 7 + 5, which is 2 coins.

    So first thing to do is sort the list from the largest to the smallest number as shown with .sort() function.

    Then for each number in that list (for loop starts with the first item in the list so the largest number) put them in a while True loop so that they keep adding to the total until condition is met:

    There are 3 conditions:

    1. current amount (from all the additions) plus the current item in the list equals the final amount, in that case increase the count by one and add the current item to total and then break out of the loop

    2. if the current amount + current item in list are bigger than the final amount just break out (this makes sure that no more of such number are added)

    3. the one that will get used the most is the one that checks if the current amount is smaller than the final one, but it is important that they are elif statements because in that case if one statement turns out to be true it doesn't check the rest which is not needed in this case because otherwise it would turn out to be true even if You couldn't add more to the current amount to not exceed the final amount.

    4. this if statement is outside of the while True loop and checks if the final amount is matched when a number 'breaks out' of the while True loop, this is to prevent continuous checking even tho the result would be already achieved.

    Then the result get evaluated and if the current amount doesn't match the final print -1 else print the count