Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Input: coins = [2], amount = 3
Output: -1

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Your code here
        pass

Solution Explanation & Interview Strategy

Approach 1: Brute-Force Recursion (Illustrative, but Inefficient)

The most intuitive approach is to try every possible combination. We can define a recursive function that explores these combinations. This approach is too slow for most platforms but is the perfect starting point to understand the need for dynamic programming.

# This is a conceptual brute-force recursion, often too slow for constraints.
# It's presented to show the thought process leading to DP.
class Solution:
    def coinChange_recursive_brute(self, coins: List[int], amount: int) -> int:
        if amount < 0: return -1
        if amount == 0: return 0
        
        min_coins = float('inf')
        
        for coin in coins:
            res = self.coinChange_recursive_brute(coins, amount - coin)
            if res != -1: # Valid path found
                min_coins = min(min_coins, res + 1)
                
        return min_coins if min_coins != float('inf') else -1

Dry Run: Brute-Force (coins = [1, 2], amount = 3)

This trace shows the call stack. `CC(n)` is a shorthand for `coinChange_recursive_brute(..., amount=n)`. Notice how `CC(1)` is computed multiple times.

CC(3)
  - coin=1: calls CC(2)
    - coin=1: calls CC(1)
      - coin=1: calls CC(0) -> returns 0
      - coin=2: calls CC(-1) -> returns -1
      - result for CC(1) is (0+1) = 1. Returns 1.
    - coin=2: calls CC(0) -> returns 0
    - min_coins for CC(2) is min(1+CC(1), 1+CC(0)) = min(1+1, 1+0) = 1. Returns 1.
  - coin=2: calls CC(1)
    - [REPEATED WORK] coin=1: calls CC(0) -> returns 0
    - [REPEATED WORK] coin=2: calls CC(-1) -> returns -1
    - result for CC(1) is (0+1) = 1. Returns 1.
- min_coins for CC(3) is min(1+CC(2), 1+CC(1)) = min(1+1, 1+1) = 2.
- Final Result: 2

The repeated computation of `CC(1)` highlights the inefficiency. DP solves this by storing the result of `CC(1)` the first time it's computed.

Approach 2: Dynamic Programming - Bottom-Up (Tabulation) - Optimal

This is the standard and efficient way to solve the problem. We build a DP table (an array), say dp, where dp[i] stores the minimum number of coins required to make amount i.

class Solution:
    def coinChange_dp_bottom_up(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for sub_amount in range(1, amount + 1):
            for coin in coins:
                if sub_amount - coin >= 0:
                    dp[sub_amount] = min(dp[sub_amount], 1 + dp[sub_amount - coin])
        
        return dp[amount] if dp[amount] != float('inf') else -1

Approach 3: Dynamic Programming - Top-Down (Recursion with Memoization)

This approach uses recursion but stores results to avoid re-computation. It can be more intuitive for some as it mirrors the brute-force thought process directly.

class Solution:
    def coinChange_dp_top_down(self, coins: List[int], amount: int) -> int:
        memo = {}

        def find_min(current_amount: int) -> int:
            if current_amount < 0: return float('inf')
            if current_amount == 0: return 0
            if current_amount in memo: return memo[current_amount]

            min_for_current_amount = float('inf')
            for coin in coins:
                res = find_min(current_amount - coin)
                if res != float('inf'):
                    min_for_current_amount = min(min_for_current_amount, 1 + res)
            
            memo[current_amount] = min_for_current_amount
            return min_for_current_amount

        result = find_min(amount)
        return result if result != float('inf') else -1

Sample Dry Run (DP Methods)

Let's trace the execution with a clear example: coins = [1, 2, 5] and amount = 6.

Dry Run: Bottom-Up DP (Tabulation)

1. Initialization:
   • `amount = 6`, so we create `dp` of size 7.
   • `dp = [float('inf'), float('inf'), float('inf'), float('inf'), float('inf'), float('inf'), float('inf')]`
   • `dp[0] = 0`
   • Initial state: `dp = [0, inf, inf, inf, inf, inf, inf]`
2. Outer loop `for sub_amount in range(1, 7)`:
   • `sub_amount = 1`:
     • `coin = 1`: `1-1 >= 0`. Update `dp[1] = min(inf, 1 + dp[0]) = 1`.
     • `coin = 2`: `1-2 < 0`. Skip.
     • `coin = 5`: `1-5 < 0`. Skip.
     • State: `dp = [0, 1, inf, inf, inf, inf, inf]`
   • `sub_amount = 2`:
     • `coin = 1`: `2-1 >= 0`. Update `dp[2] = min(inf, 1 + dp[1]) = 2`.
     • `coin = 2`: `2-2 >= 0`. Update `dp[2] = min(2, 1 + dp[0]) = 1`.
     • `coin = 5`: `2-5 < 0`. Skip.
     • State: `dp = [0, 1, 1, inf, inf, inf, inf]`
   • `sub_amount = 3`:
     • `coin = 1`: `3-1 >= 0`. Update `dp[3] = min(inf, 1 + dp[2]) = 1 + 1 = 2`.
     • `coin = 2`: `3-2 >= 0`. Update `dp[3] = min(2, 1 + dp[1]) = min(2, 1 + 1) = 2`.
     • `coin = 5`: `3-5 < 0`. Skip.
     • State: `dp = [0, 1, 1, 2, inf, inf, inf]`
   • `sub_amount = 4`:
     • `coin = 1`: `4-1 >= 0`. Update `dp[4] = min(inf, 1 + dp[3]) = 1 + 2 = 3`.
     • `coin = 2`: `4-2 >= 0`. Update `dp[4] = min(3, 1 + dp[2]) = min(3, 1 + 1) = 2`.
     • `coin = 5`: `4-5 < 0`. Skip.
     • State: `dp = [0, 1, 1, 2, 2, inf, inf]`
   • `sub_amount = 5`:
     • `coin = 1`: `5-1 >= 0`. Update `dp[5] = min(inf, 1 + dp[4]) = 1 + 2 = 3`.
     • `coin = 2`: `5-2 >= 0`. Update `dp[5] = min(3, 1 + dp[3]) = min(3, 1 + 2) = 3`.
     • `coin = 5`: `5-5 >= 0`. Update `dp[5] = min(3, 1 + dp[0]) = min(3, 1 + 0) = 1`.
     • State: `dp = [0, 1, 1, 2, 2, 1, inf]`
   • `sub_amount = 6`:
     • `coin = 1`: `6-1 >= 0`. Update `dp[6] = min(inf, 1 + dp[5]) = 1 + 1 = 2`.
     • `coin = 2`: `6-2 >= 0`. Update `dp[6] = min(2, 1 + dp[4]) = min(2, 1 + 2) = 2`.
     • `coin = 5`: `6-5 >= 0`. Update `dp[6] = min(2, 1 + dp[1]) = min(2, 1 + 1) = 2`.
     • State: `dp = [0, 1, 1, 2, 2, 1, 2]`
3. Final Step:
   • The loops finish. The final array is `dp = [0, 1, 1, 2, 2, 1, 2]`.
   • `dp[amount]` is `dp[6]`, which is `2`.
   • `2 != float('inf')` is true.
   • Return `2`. (Correct, as 6 = 5 + 1).

Dry Run: Top-Down DP (Memoization)

This trace shows the recursion stack. `->` indicates a call, `<-` indicates a return. `memo` starts as `{}`.

find_min(6)
  -> find_min(5)  // using coin 1
    -> find_min(4)  // using coin 1
      -> find_min(3)  // using coin 1
        -> find_min(2)  // using coin 1
          -> find_min(1)  // using coin 1
            -> find_min(0)  // using coin 1
            <- returns 0
            -> find_min(-1) // using coin 2, returns inf
            -> find_min(-4) // using coin 5, returns inf
            memo[1] = 1, returns 1
          <- returns 1
          -> find_min(0)  // using coin 2
          <- returns 0
          min for 2 becomes min(inf, 1+1), then min(2, 1+0) = 1
          memo[2] = 1, returns 1
        <- returns 1
        -> find_min(1) // using coin 2
           (1 is in memo!) <- returns memo[1] which is 1
        min for 3 becomes min(inf, 1+1=2), then min(2, 1+1=2) = 2
        memo[3] = 2, returns 2
      <- returns 2
      -> find_min(2) // using coin 2
         (2 is in memo!) <- returns memo[2] which is 1
      min for 4 becomes min(inf, 1+2=3), then min(3, 1+1=2) = 2
      memo[4] = 2, returns 2
    <- returns 2
    -> find_min(3) // using coin 2
       (3 is in memo!) <- returns memo[3] which is 2
    -> find_min(0) // using coin 5
    <- returns 0
    min for 5 becomes min(inf, 1+2=3), then min(3, 1+2=3), then min(3, 1+0=1) = 1
    memo[5] = 1, returns 1
  <- returns 1
  -> find_min(4) // using coin 2
     (4 is in memo!) <- returns memo[4] which is 2
  -> find_min(1) // using coin 5
     (1 is in memo!) <- returns memo[1] which is 1
  min for 6 becomes min(inf, 1+1=2), then min(2, 1+2=3), then min(2, 1+1=2) = 2
  memo[6] = 2, returns 2
<- final result from find_min(6) is 2

Final check: result (2) is not inf. Return 2.