Coin Change | Dynamic Programming

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;
}

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Notice that while calculating:

solve(11)

Enter fullscreen mode Exit fullscreen mode

we repeatedly calculate:

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

Enter fullscreen mode Exit fullscreen mode

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]

Enter fullscreen mode Exit fullscreen mode

stores:

Minimum coins needed to make target

Enter fullscreen mode Exit fullscreen mode

Transition

For every coin:

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

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

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

Enter fullscreen mode Exit fullscreen mode

Recursive Choices

11

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

Enter fullscreen mode Exit fullscreen mode

Eventually:

11
=
5 + 5 + 1

Enter fullscreen mode Exit fullscreen mode

Coins used:

3

Enter fullscreen mode Exit fullscreen mode

Result

Minimum Coins = 3

Enter fullscreen mode Exit fullscreen mode

DP Visualization

dp[1] = 1

dp[2] = 1

dp[3] = 2

dp[4] = 2

dp[5] = 1

...

dp[11] = 3

Enter fullscreen mode Exit fullscreen mode

Each state is calculated only once.

Why Memoization Works?

Without DP:

solve(10)

Enter fullscreen mode Exit fullscreen mode

might be computed hundreds of times.

With Memoization:

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

Enter fullscreen mode Exit fullscreen mode

This eliminates redundant work and drastically improves performance.

Complexity Analysis

Metric Complexity Time Complexity O(N × Amount) Space Complexity O(Amount)

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

Enter fullscreen mode Exit fullscreen mode

Similar Problems

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