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.

https://stackoverflow.com/questions/67067229/issue-in-the-top-down-approach-to-the-coin-change-similar-to-the-0-1-backpack-p April 13, 2021 at 08:26AM