Problem Statement

Given an array of coin denominations coins[] and an integer amount, return the minimum number of coins required to make up that amount.

If it is not possible to form the amount, return -1.

You can use a coin unlimited number of times.

Brute Force Intuition

For every amount, try using each available coin and recursively solve for the remaining amount.

At each step, we explore all possible choices and take the minimum coins among all valid combinations.

The same subproblems get solved repeatedly, making the recursive solution extremely slow.

Complexity

• Time Complexity: O(N^Amount)
• Space Complexity: O(Amount)

Brute Force Snippet

int solve(int[] coins, int target) {

 if (target == 0)
 return 0;

 if (target < 0)
 return Integer.MAX_VALUE;

 int min = Integer.MAX_VALUE;

 for (int coin : coins) {

 int ans = solve(coins, target - coin);

 if (ans != Integer.MAX_VALUE) {
 min = Math.min(min, 1 + ans);
 }
 }

 return min;
}

Moving Towards the Optimal Approach

Notice that while calculating:

solve(11)

we repeatedly calculate:

solve(10)
solve(9)
solve(8)
...

multiple times.

Since the answer for a target never changes, we can store it and reuse it whenever needed.

This is exactly where Dynamic Programming (Memoization) helps.

DP Pattern Recognition

Whenever you see:

• Minimum / Maximum answer
• Multiple choices at every step
• Same subproblems repeating

Think:

Recursion + Memoization

Optimal Approach (Top Down DP)

State

dp[target]

stores:

Minimum coins needed to make target

Transition

For every coin:

dp[target]
=
1 + dp[target - coin]

Take the minimum among all possible choices.

Optimal Java Solution

import java.util.*;

class Solution {

 public int coinChange(int[] coins, int amount) {

 int[] dp = new int[amount + 1];
 Arrays.fill(dp, -1);

 int ans = solve(coins, amount, dp);

 return ans == Integer.MAX_VALUE ? -1 : ans;
 }

 private int solve(int[] coins, int target, int[] dp) {

 if (target == 0)
 return 0;

 if (target < 0)
 return Integer.MAX_VALUE;

 if (dp[target] != -1)
 return dp[target];

 int min = Integer.MAX_VALUE;

 for (int coin : coins) {

 int ans = solve(coins, target - coin, dp);

 if (ans != Integer.MAX_VALUE) {
 min = Math.min(min, 1 + ans);
 }
 }

 return dp[target] = min;
 }
}

Dry Run

Input

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

Recursive Choices

11

Using 1 → solve(10)
Using 2 → solve(9)
Using 5 → solve(6)

Eventually:

11
=
5 + 5 + 1

Coins used:

3

Result

Minimum Coins = 3

DP Visualization

dp[1] = 1

dp[2] = 1

dp[3] = 2

dp[4] = 2

dp[5] = 1

...

dp[11] = 3

Each state is calculated only once.

Why Memoization Works?

Without DP:

solve(10)

might be computed hundreds of times.

With Memoization:

First Time -> Compute
Next Time -> Return dp[10]

This eliminates redundant work and drastically improves performance.

Complexity Analysis

Where:

• N = Number of Coins
• Amount = Target Amount

Interview One-Liner

For every target amount, try all coins and recursively solve the remaining amount. Use memoization to avoid recomputing the same target multiple times.

Pattern Learned

Choice at every step
+
Minimum answer required
+
Overlapping subproblems

=> Dynamic Programming

Similar Problems

• Minimum Coins
• Perfect Squares
• Minimum Cost Climbing Stairs
• Rod Cutting
• Unbounded Knapsack