Jaspreet singh

Posted on Jun 16

Coin Change | Dynamic Programming

#algorithms #computerscience #leetcode #tutorial

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:

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

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

DEV Community