Coin Change | Leetcode 322

Welcome to our deep dive into Coin Change (Leetcode 322). If you want to understand how Dynamic Programming handles infinite supply combinatorics, this is strictly the most critical problem to practice.

Problem Statement

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: coins = [1, 2, 5], amount = 11 => Output: 3 (Explanation: 11 = 5 + 5 + 1).

Approach 1: Top-Down Recursion with Memoization O(A * C)

If we think about this problem natively, to find the absolute minimum coins for amount = 11 using coins [1, 2, 5], we literally just check three separate branches:

1. 1 + min_coins(amount - 1)
2. 1 + min_coins(amount - 2)
3. 1 + min_coins(amount - 5)

Because amount - 1 and amount - 2 could eventually calculate the exact same smaller subproblems, a pure DFS tree will mathematically explode repeatedly calculating identical numbers. We can use a Memoization Dictionary (cache) to memorize the results of subproblems!

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        memo = {}
        
        def dfs(remainder):
            # Base cases
            if remainder == 0: return 0
            if remainder < 0: return float('inf')
            
            # Check cached computations
            if remainder in memo:
                return memo[remainder]
                
            min_cost = float('inf')
            # Test all potential branches dynamically!
            for coin in coins:
                result = dfs(remainder - coin)
                if result != float('inf'):
                    min_cost = min(min_cost, result + 1)
                    
            memo[remainder] = min_cost
            return min_cost
            
        ans = dfs(amount)
        return ans if ans != float('inf') else -1

Complexity Analysis

Approach 2: Bottom-Up DP O(A * C)

Instead of working backward from 11 and drilling to 0 with heavy recursion stacks, we just execute Bottom-Up tabulation.

We spawn a dp array scaled from [0...amount], initialized to Infinity because we want to aggressively seek the min. dp[0] = 0 (it takes 0 coins to make $0). We natively loop up sequentially from 1 to amount. At every target amount, we iterate through all available coins. If amount - coin is accessible, dp[target] is explicitly mathematically set to the strict min of its current value vs 1 + dp[amount - coin]!

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Initialize array to absolute Amount + 1. 
        # (This is a safer 'Infinity' because the max coins possible is mathematically 'amount' via pennies!)
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        
        # Build natively upward layer-by-layer
        for a in range(1, amount + 1):
            for c in coins:
                # If the coin conceptually fits inside the current target amount
                if a - c >= 0:
                    dp[a] = min(dp[a], 1 + dp[a - c])
                    
        return dp[amount] if dp[amount] != amount + 1 else -1

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (322)