Introduction

The Coin Change problem is one of the most famous Dynamic Programming interview questions.

You are given:

coins[] and amount

Goal:

Find the minimum number of coins required to make the amount.

If impossible:

Return -1

Example

coins = [1,2,5]
amount = 11
Output = 3

Explanation:

11 = 5 + 5 + 1
Total Coins = 3

Constraints

1 <= coins.length <= 120 <= amount <= 10^4

Key Observation

To form amount:

i

Try every coin:

coin

If coin can be used:

dp[i] = min(dp[i],1 + dp[i - coin])

This creates the DP recurrence.

Approach : Dynamic Programming

Explanation

For each amount:

  1. Try every coin.
  2. Check if coin fits.
  3. Use previously solved answer.
  4. Update minimum coins.

Dry Run

Input:

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

DP Table:

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

Answer:

3

Using:

5 + 5 + 1

Practice

Complexity Analysis

Memoization
Time Complexity: O(amount × n)
Space Complexity: O(amount)

Tabulation
Time Complexity: O(amount × n)
Space Complexity: O(amount)

Space Optimized DP
Time Complexity: O(amount × n)
Space Complexity: O(amount)

where:
n = number of coins

Why This Problem is Important

This problem teaches:

  • Unbounded DP
  • Optimization Problems
  • State Transitions
  • Minimum Operations
  • Dynamic Programming Design

Common Beginner Mistakes

  • Using greedy approach
  • Wrong initialization
  • Forgetting impossible cases
  • Using maximum instead of minimum
  • Not checking coin bounds

Interview Tip

Always explain:

Try every coin and reuse smaller answers.

This is the foundation of:

Unbounded Knapsack DP

Related Questions

  • Decode Ways
  • House Robber
  • House Robber II
  • Climbing Stairs
  • Fibonacci

Final Takeaway

Coin Change is one of the most important Dynamic Programming interview problems.

It teaches:

  • DP state design
  • optimization strategies
  • minimum operations pattern
  • unbounded decision making

Mastering Coin Change prepares you for advanced DP and Knapsack-style interview questions.