Coin change problem comparison of top-down approaches

Question

I'm working on LeetCode 322: Coin Change.

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:

Input: coins = [1,2,5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

I choose a top-down approach where at each iteration I choose a coin whose denomination is not greater than the remaining amount. Sounds easy, right?

The following code passes all test cases.

import sys
import functools

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @functools.cache   
        def _loop(remaining: int) -> int:
            if remaining == 0:
                return 0
            y = sys.maxsize
            for coin in filter(lambda x: x <= remaining, coins):
                y = min(y, _loop(remaining - coin))

            return (y + 1) if y < sys.maxsize else y
        
        num_coins = _loop(amount)
        return num_coins if num_coins < sys.maxsize else -1

But this one doesn't.

import sys
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        num_coins = self._loop(coins, amount, 0, {})
        return num_coins if num_coins < sys.maxsize else -1
    
    def _loop(self, coins: Sequence[int], remaining: int, count: int, memo: MutableMapping[int, int]) -> int:
        if remaining == 0:
            return count
        if remaining not in memo:
            y = sys.maxsize
            for coin in filter(lambda x: x <= remaining, coins):
                y = min(y, self._loop(coins, remaining - coin, count + 1, memo))
            memo[remaining] = y

        return memo[remaining]

The only difference between the two solutions is that in the former, 1 is added to the result after the for loop (because one coin has been used), and in the latter, 1 is added to the parameter to the recursive call.

What is the bug in the second solution that I'm not seeing?

Tejas Narayanan Tejas Narayanan · Accepted Answer · 2021-09-28T01:01:50

Based on the way you are using memo, memo[x] is meant to contain the minimum number of coins needed to total x cents. However, this is not what is happening.

Let's look at the recursion stack:

remaining = 4, count = 0, y = maxsize, take coin 1:
    remaining = 3, count = 1, y = maxsize, take coin 1:
        remaining = 2, count = 2, y = maxsize, take coin 1:
            remaining = 1, count = 3, y = maxsize, take coin 1:
                remaining = 0, count = 4, RETURN 4
            y = 4, memo[1] = 4, RETURN 4
        remaining = 2, count = 2, y = 4, take coin 2:
            remaining = 0, count = 3, RETURN 3
        y = 3, memo[2] = 3, RETURN 3
    remaining = 3, count = 1, y = 3, take coin 2:
        remaining = 1, count = 2, memo[1] exists, RETURN 4
    y = 3, memo[3] = 3, RETURN 3
remaining = 4, count = 0, y = 3, take coin 2:
    remaining = 2, count = 1, memo[2] exists, RETURN 3
y = 3, memo[4] = 3, RETURN 3

See the problem? memo doesn't have the right values in them. memo[1] should be 1, but instead the code is setting it to 4. Similarly, memo[3] should be 2, but instead the code is setting it to 3.

To use a memo array like you're using, it would be much easier to work from the bottom-up: start with a base condition (memo[0] = 0), and calculate the values of memo[1], memo[2], ... memo[amount] based on the previously calculated values.

Coin change problem comparison of top-down approaches

1 Answers