🪙Coin Change

Question (LC.322)

Given a list of coin denominations and a desired amount, return the fewest number of coins that can make up the desired amount.

Examples

I: coins = [1, 2, 5], amount = 11
O: 3 (5 + 5 + 1) 

I: coins = [2], amount = 3
O: -1 (not possible) 

I: coins = [1], amount = 0 
O: 0 

Approach

The easiest way to come up with an approach is to see the search graph or the search tree.

Coin Change Search Tree

D&C

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        min_change = self.search_num_coins(coins, amount)
        if min_change is not None:
            return min_change
        return -1

    def search_num_coins(self, coins: List[int], amount: int) -> Optional[int]:
        # base case
        if amount < 0:
            return None

        if amount == 0:
            return 0

        min_change = None

        # divide
        for c in coins:
            num_change = self.search_num_coins(coins, amount - c)
            # merge
            if num_change is not None:
                if min_change is None:
                    min_change = 1 + num_change
                else:
                    min_change = min(min_change, 1 + num_change)

        return min_change

this algo is exponential and the exponent is the depth

if the recursion depth is too high, then this approach is not functional.

for example [2,3,6,7], 77 can cause a TLE on the OJ

Memoized Search

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        memo: Dict[int, Optional[int]] = {}
        min_change = self.search_num_coins(coins, amount, memo)
        if min_change is not None:
            return min_change
        return -1

    def search_num_coins(
        self, coins: List[int], amount: int, memo: Dict[int, Optional[int]]
    ) -> Optional[int]:
        # base case
        if amount < 0:
            return None

        if amount in memo:
            return memo[amount]

        if amount == 0:
            return 0

        min_change = Nonepy

        # divide
        for c in coins:
            num_change = self.search_num_coins(coins, amount - c, memo)
            # merge
            if num_change is not None:
                if min_change is None:
                    min_change = 1 + num_change
                else:
                    min_change = min(min_change, 1 + num_change)

        memo[amount] = min_change
        return min_change

time is bounded pseudo polynomial

Greedy Boost

significantly reduce the search depth

for example [1,2,4], 32000

DP

# define by value
# dp[a] = the minimum number of coins to sum to amount a

# recursive step
# dp[a] = min(1 + dp[a-c] for all c in coins)

# base case
# dp[0] = 0

# topo order
# for a from 0 to amount

# final answer
# dp[amount]

def coinChange(self, coins: List[int], amount: int) -> int:
    dp: Dict[int, int] = {}

    # init
    dp[0] = 0

    # topo order
    for a in range(amount):
        if a not in dp:
            continue
        for c in coins:
            if a + c > amount:
                continue
            if a + c in dp:
                dp[a + c] = min(dp[a + c], 1 + dp[a])
            else:
                dp[a + c] = 1 + dp[a]

    if amount in dp:
        return dp[amount]
    return -1