Coin Change

Master this topic with zero to advance depth.

Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Visual Representation

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

Optimal: 5 + 5 + 1 = 11 (3 coins)

DP Strategy:
To make amount 11, we can take:
- Coin 1: 1 + minCoins(10)
- Coin 2: 1 + minCoins(9)
- Coin 5: 1 + minCoins(6)
We take the minimum of these choices.

Medium

Examples

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

Input: coins = [2], amount = 3
Output: -1

Approach 1

Level I: Brute Force (Recursive)

Intuition

For each coin, we try taking it and then recursively solve for the remaining amount. We try all coins for each state and keep the minimum result.

Thought Process

solve(amt) = 1 + min(solve(amt - coin)) for all coin in coins.
Base cases: If amt == 0, return 0. If amt < 0, return infinity.

Pattern Identification

This is Recursive Exhaustive Search. It explores many redundant paths (e.g., to reach amount 5, you might do 2+2+1, 2+1+2, 1+2+2, etc.).

⏱ O(S^n) where S is amount and n is number of coins💾 O(S) for recursion depth

Detailed Dry Run

coins=[1, 2], amt=3

Call	amt	Choices	Returns
1	3	1+f(2), 1+f(1)	min(2, 2) = 2
2	2	1+f(1), 1+f(0)	min(2, 1) = 1
3	1	1+f(0), 1+f(-1)	min(1, inf) = 1
4	0	-	0 (Base Case)

java

public class Main {
    public static int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return 100000; // Represent Infinity

        int minCoins = 100000;
        for (int coin : coins) {
            int res = coinChange(coins, amount - coin);
            if (res != 100000) {
                minCoins = Math.min(minCoins, 1 + res);
            }
        }
        return minCoins;
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int res = coinChange(coins, 11);
        System.out.println(res >= 100000 ? -1 : res);
    }
}

Approach 2

Level II: Top-Down DP (Memoization)

Intuition

The brute-force recursion recalculates the same amount values repeatedly. We store results in a memo map/array to skip recomputation.

Visual

coins=[1,2], amount=4
tree (without memo):           | with memo:
         f(4)                  | f(4) calls f(3), f(2)
        /    \                | f(3) already done in f(4)!
     f(3)    f(2)              | Skipped!
     / \    / \              |
  f(2) f(1) f(1) f(0)          |

⏱ O(Amount * n)💾 O(Amount)

Detailed Dry Run

coins=[1,2], amount=3. memo[2] = min(1+memo[1], 1+memo[0]) = 1. memo[3] = min(1+memo[2], 1+memo[1]) = 2.

java

import java.util.*;

public class Main {
    static int[] memo;
    public static int solve(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if (memo[amount] != Integer.MAX_VALUE) return memo[amount];
        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = solve(coins, amount - coin);
            if (res != -1) minCoins = Math.min(minCoins, res + 1);
        }
        return memo[amount] = (minCoins == Integer.MAX_VALUE ? -1 : minCoins);
    }

    public static int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        return solve(coins, amount);
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11)); // 3
    }
}

⚠️ Common Pitfalls & Tips

Use a sentinel value (not -1) to differentiate 'not computed yet' from 'impossible'. Using -2 or INT_MAX as the uncomputed signal works well.

Approach 3

Level III: Optimal (Bottom-Up DP)

Intuition

Thought Process

We build the solution for all amounts from 1 to targetAmount. For each amount i, we check which coin was the last one added. The minimum coins for i will be 1 + dp[i - coin].

Logic Steps

Initialize a dp array of size amount + 1 with a large value (e.g., amount + 1).
Set dp[0] = 0 (base case).
Loop through each amount i from 1 to amount.
For each i, loop through each coin.
If i - coin >= 0, update dp[i] = min(dp[i], 1 + dp[i - coin]).
Return dp[amount] or -1 if unreachable.

⏱ O(Amount * n) where n is number of coins💾 O(Amount)

Detailed Dry Run

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

i	Coins Loop	dp[i] calculation	Result
1	1	1 + dp[0] = 1	1
2	1, 2	min(1+dp[1], 1+dp[0])	1
3	1, 2	min(1+dp[2], 1+dp[1])	2
4	1, 2	min(1+dp[3], 1+dp[2])	2
5	1, 2, 5	min(1+dp[4], 1+dp[3], 1+dp[0])	1

java

import java.util.Arrays;

public class Main {
    public static int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11)); // 3
    }
}

⚠️ Common Pitfalls & Tips

Be very careful with the initialization of the dp array. Using Integer.MAX_VALUE in Java or 1e9 can cause integer overflow when you do 1 + dp[i-coin]. Using amount + 1 is a safer 'infinity' for this problem.

← Previous QuestionUnique Paths

Next Question →House Robber

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.