How do you solve Coin Change?

Implement a recursive function dp(rem) that returns the minimum coins needed for rem. Base cases handle rem < 0 (impossible) and rem == 0 (zero coins). For each coin, recursively compute dp(rem - coin), and take the minimum result plus one. Memoize results to ensure each subproblem is solved once. Finally, return dp(amount) or -1 if no solution exists.

What pattern does Coin Change use?

The Pattern: Dynamic Programming (Top-Down Memoization) The Heuristic: When a problem involves finding an optimal value over overlapping subproblems with recursive dependencies, use memoization to cache results and avoid exponential recomputation, transforming brute-force recursion into efficient DP.

Coin Change — Dynamic Programming

Q: What is the time complexity of Coin Change?

O(amount * n). Each amount from 0 to amount is computed at most once, and for each amount, the algorithm iterates over all n coin denominations, resulting in O(amount * n) time.

Q: What pattern does Coin Change use?

The Pattern: Dynamic Programming (Top-Down Memoization) The Heuristic: When a problem involves finding an optimal value over overlapping subproblems with recursive dependencies, use memoization to cache results and avoid exponential recomputation, transforming brute-force recursion into efficient DP.

Problem

Given an integer array coins representing coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If the amount cannot be made up by any combination of the coins, return -1.

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 2³¹ - 1
0 ≤ amount ≤ 10⁴

Example

Input: coins = [1, 2, 5], amount = 11

Output: 3

The brute-force approach tries all combinations of coins to sum to 11, which is exponential and inefficient. The optimal solution uses recursion with memoization to avoid redundant calculations. For example, to compute dp(11), the algorithm tries dp(10), dp(9), and dp(6) by subtracting coins 1, 2, and 5 respectively. Each subproblem is solved once and cached. The critical moment is when dp(6) is computed, which itself depends on smaller amounts. By caching results, the algorithm avoids recomputing dp(6) multiple times, drastically reducing the total work. The final answer is dp(11) = 3, corresponding to coins [5,5,1].

Approach

Straightforward Solution

A brute-force recursive approach tries all combinations of coins to sum to the amount, leading to exponential time complexity because it recomputes the same subproblems multiple times.

Core Observation

The minimum number of coins needed for amount A depends on the minimum number needed for smaller amounts A - coin, for each coin denomination. This recursive dependency forms overlapping subproblems with optimal substructure, making Dynamic Programming the natural fit.

Path to Optimal

Preview

Recognizing overlapping subproblems, memoization caches results of dp(rem) calls to avoid redundant work. The problem is reframed as: for each amount rem, find the minimum among dp(rem - coin) + 1 for all coins…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a recursive function dp(rem) that returns the minimum coins needed for rem. Base cases handle rem < 0 (impossible) and rem == 0 (zero coins)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(amount * n)

Each amount from 0 to amount is computed at most once, and for each amount, the algorithm iterates over all n coin denominations, resulting in O(amount * n) time.

Space

O(amount)

The memoization dictionary stores results for each amount up to the target, requiring O(amount) auxiliary space. The recursion stack depth is at most amount, which is also O(amount).

Solution

Python

1class Solution:
  def coinChange(self, coins: list[int], amount: int) -> int:
      memo = {}
4
      def dp(rem):
          if rem < 0:
              return float('inf')
          if rem == 0:
              return 0
          if rem in memo:
              return memo[rem]
          
          min_coins = float('inf')
          for coin in coins:
              res = dp(rem - coin)
              if res != float('inf'):
                  min_coins = min(min_coins, res + 1)
          
          memo[rem] = min_coins
          return min_coins
      
      result = dp(amount)
      return result if result != float('inf') else -1

Step-by-Step Solution

1

Initialize Memoization Cache and Define Recursive DP Function

3memo = {}
5def dp(rem):
  if rem < 0:
      return float('inf')
  if rem == 0:
      return 0
  if rem in memo:
      return memo[rem]

Objective

To set up a cache for storing computed results and define the recursive function that computes the minimum coins for a given remainder.

Key Insight

Memoization is essential to avoid recomputing the minimum coins for the same remainder multiple times. Defining the recursive dp(rem) function encapsulates the problem of finding the minimum coins for any sub-amount rem, enabling a clean top-down DP approach.

Interview Quick-Check

Core Logic

Memoization cache stores results for each remainder to ensure each subproblem is solved once.

State & Boundaries

The dp function handles base cases for rem < 0 (impossible) and rem == 0 (zero coins).

Common Pitfalls & Bugs

Forgetting to check the memo before recursion leads to exponential time complexity.

2

Compute Minimum Coins by Exploring All Coin Choices

To recursively compute the minimum coins needed for the current remainder by trying all coin denominations and selecting the best option.

3

Cache Computed Result and Return Final Answer

To store the computed minimum coins for the current remainder in the memo and return the final result for the original amount.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical

memo = {}

Initialize a dictionary to memoize results for subproblems.

This cache is critical to store the minimum coins needed for each remainder, preventing redundant recursive calls and reducing exponential complexity to polynomial.

Line 5 Critical

def dp(rem):

Define the recursive function dp that computes minimum coins for remainder rem.

Encapsulating the problem as dp(rem) allows a clean top-down dynamic programming approach that naturally expresses the problem's optimal substructure.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why is memoization critical in this recursive solution for coin change?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Coin Change from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Coin Change drill

or drill a free problem

1	`class Solution:`
2	`def coinChange(self, coins: list[int], amount: int) -> int:`
3	`memo = {}`
4
5	`def dp(rem):`
6	`if rem < 0:`
7	`return float('inf')`
8	`if rem == 0:`
9	`return 0`
10	`if rem in memo:`
11	`return memo[rem]`
12
13	`min_coins = float('inf')`
14	`for coin in coins:`
15	`res = dp(rem - coin)`
16	`if res != float('inf'):`
17	`min_coins = min(min_coins, res + 1)`
18
19	`memo[rem] = min_coins`
20	`return min_coins`
21
22	`result = dp(amount)`
23	`return result if result != float('inf') else -1`

3	`memo = {}`
5	`def dp(rem):`
6	`if rem < 0:`
7	`return float('inf')`
8	`if rem == 0:`
9	`return 0`
10	`if rem in memo:`
11	`return memo[rem]`