Coin Change

The problem description can be found in LeetCode.

Approach

A simple greedy approach would consist of start picking the coin with the highest values and then use the other ones.

Otherwise, this won't give us an optional solution for every input. In fact, suppose having this example:

coins = [5, 4, 1]
amount = 8

If we start from the most valuable coin, we would have [5, 1, 1, 1]. However, if we pick 4, we would have [4, 4].

So, a brute force approach would consist of checking all possible values that sum up to the target amount and then choose the path with the shortest number of coins.

Let's derive the partial space tree:

exampleroot8l1_33root--l1_35l1_44root--l1_44l1_77root--l1_71l2_3_min2-2l1_3--l2_3_min25l2_3_min1-1l1_3--l2_3_min14l2_3_12l1_3--l2_3_11l2_4_min1-1l1_4--l2_4_min15l2_4_00l1_4--l2_4_04l2_4_33l1_4--l2_4_31l2_7_22l1_7--l2_7_25l2_7_33l1_7--l2_7_34l2_7_66l1_7--l2_7_61

Where we marked the following:

  • Yellow: the repeated work for an amount of 3.
  • Orange: the repeated work for an amount of 2.
  • Green: a valid solution.

This repeated work suggests that we can apply Dynamic Programming.

Solution

from typing import Dict, List


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def dfs(curr_amount: int, memo: Dict[int, int]) -> int:
            if curr_amount in memo:
                return memo[curr_amount]
            if curr_amount == 0:
                return 0
            if curr_amount < 0:
                return float("+inf")

            min_coins = float("+inf")
            for coin in coins:
                min_coins = min(min_coins, 1 + dfs(curr_amount - coin, memo))

            memo[curr_amount] = min_coins
            return memo[curr_amount]

        num_coins = dfs(amount, {})
        return num_coins if num_coins != float("+inf") else -1

Complexity

  • Time:
  • Space:

Where and is the size of the coins list.