Solution 1: Dynamic Programming

Intuition:

To solve the Coin Change problem, we can use dynamic programming. We’ll create an array dp of size amount + 1, where dp[i] represents the minimum number of coins needed to make up the amount i. We’ll initialize all values in dp to be equal to infinity except for dp[0], which will be set to 0. Then, we’ll iterate through each coin denomination and update the dp array for each amount starting from the coin denomination value. We’ll update dp[i] by taking the minimum between dp[i] and dp[i - coin] + 1, where coin is the current denomination. Finally, we’ll return dp[amount] as the minimum number of coins needed to make up the target amount.

Solution:

from typing import List

def coin_change(coins: List[int], amount: int) -> int:
    # Initialize the dp array with infinity
    dp = [float('inf')] * (amount + 1)
    # Base case: 0 amount needs 0 coins
    dp[0] = 0
    
    # Iterate through each coin denomination
    for coin in coins:
        # Update dp array for each amount starting from the coin denomination value
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # If dp[amount] is still infinity, it means the amount cannot be made up
    return dp[amount] if dp[amount] != float('inf') else -1

# Test cases
print(coin_change([1, 2, 5], 11))  # Output: 3 (11 = 5 + 5 + 1)
print(coin_change([2], 3))         # Output: -1 (Not possible)
print(coin_change([1], 0))         # Output: 0 (0 amount needs 0 coins)
print(coin_change([1], 1))         # Output: 1 (1 amount needs 1 coin)

Time Complexity:

  • Let n be the number of coin denominations, m be the target amount.
  • We iterate through each coin denomination and for each denomination, we iterate through each amount from 1 to m, resulting in a time complexity of O(n * m).
  • Therefore, the time complexity is O(n * m).

Space Complexity:

  • We use an additional array dp of size m + 1, resulting in a space complexity of O(m).
  • Additionally, we use O(1) extra space for variables and function calls.
  • Therefore, the overall space complexity is O(m).

Solution 2: Depth-First Search with Memoization

Intuition:

Another approach to solve the Coin Change problem is using recursion with memoization (top-down dynamic programming). We can define a recursive function that tries all possible combinations of coins to make up the target amount. We’ll use memoization to store the results of subproblems to avoid redundant calculations.

Solution:

from typing import List

def coin_change(coins: List[int], amount: int) -> int:
    # Dictionary to store memoized results
    memo = {}
    
    def dfs(amount: int) -> int:
        # Base case: If the amount is 0, no coins needed
        if amount == 0:
            return 0
        # If the amount is negative or no coins available, return -1 (invalid)
        if amount < 0 or not coins:
            return -1
        # If the result is already memoized, return it
        if amount in memo:
            return memo[amount]
        
        # Initialize the minimum number of coins needed to infinity
        min_coins = float('inf')
        # Try each coin denomination
        for coin in coins:
            # Recursively calculate the minimum number of coins needed for the remaining amount
            result = dfs(amount - coin)
            # If the result is valid and less than the current minimum, update the minimum
            if result >= 0 and result < min_coins:
                min_coins = result + 1
        
        # Memoize the result and return it
        memo[amount] = min_coins if min_coins != float('inf') else -1
        return memo[amount]
    
    # Call the recursive function with the target amount
    return dfs(amount)

# Test cases
print(coin_change([1, 2, 5], 11))  # Output: 3 (11 = 5 + 5 + 1)
print(coin_change([2], 3))         # Output: -1 (Not possible)
print(coin_change([1], 0))         # Output: 0 (0 amount needs 0 coins)
print(coin_change([1], 1))         # Output: 1 (1 amount needs 1 coin)

Time Complexity:

This solution has the same time complexity as the previous dynamic programming solution:

  • Let n be the number of coin denominations, m be the target amount.
  • The recursion tree has a height of amount, which is m.
  • At each level of the recursion tree, we have to try each coin denomination, leading to a branching factor of len(coins), or n.
  • At each node of the recursion tree, we perform constant-time operations to calculate the result.
  • Therefore, the time complexity is proportional to the product of the height of the recursion tree, m, and the branching factor, n, which is O(n * m).

Space Complexity:

This solution has the same space complexity as the previous dynamic programming solution. The space complexity primarily depends on:

  • The space used by the memoization dictionary: In the worst case, all amounts from 0 to amount will be stored in the memoization dictionary. Therefore, the space required for memoization is O(amount) or O(m).
  • The space used by the recursion stack: The depth of the recursion stack is proportional to the height of the recursion tree, which is amount.

Therefore, the overall space complexity is O(m) due to memoization and O(m) due to recursion stack space, leading to a total space complexity of O(m).