Approach

Coin Change

Problem Statement

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.

Examples

Example 1:

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

Example 2:

Input: coins = [2], amount = 3
Output: -1
Explanation: Cannot make amount 3 with only coins of denomination 2.

Example 3:

Input: coins = [1], amount = 0
Output: 0
Explanation: No coins needed for amount 0.

Constraints

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 2^31 - 1
0 ≤ amount ≤ 10^4

Approach

Key Insight

This is an Unbounded Knapsack problem!

For each amount, we try every coin and take the minimum:

dp[amount] = min(dp[amount - coin] + 1) for each coin that fits

Solution 1: Dynamic Programming (Bottom-Up)

Build the solution from amount 0 to target.

Algorithm:

Create DP array of size amount + 1, initialize with infinity
Base case: dp[0] = 0 (0 coins needed for amount 0)
For each amount from 1 to target:
- For each coin:
  - If coin ≤ amount:
    - dp[amount] = min(dp[amount], dp[amount - coin] + 1)
Return dp[amount] if not infinity, else -1

Solution 2: BFS Approach

Treat it as a shortest path problem!

Algorithm:

Use BFS starting from amount 0
For each amount, try adding each coin
Track visited amounts to avoid reprocessing
Return level (number of coins) when we reach target

Visualization Example

For coins = [1, 2, 5] and amount = 11:

dp[0] = 0   (base case)
dp[1] = 1   (1 coin: 1)
dp[2] = 1   (1 coin: 2)
dp[3] = 2   (2 coins: 2+1)
dp[4] = 2   (2 coins: 2+2)
dp[5] = 1   (1 coin: 5)
dp[6] = 2   (2 coins: 5+1)
dp[7] = 2   (2 coins: 5+2)
dp[8] = 3   (3 coins: 5+2+1)
dp[9] = 3   (3 coins: 5+2+2)
dp[10] = 2  (2 coins: 5+5)
dp[11] = 3  (3 coins: 5+5+1)

Complexity Analysis

DP Solution:

Time Complexity: O(amount × coins.length) - try each coin for each amount
Space Complexity: O(amount) - DP array

BFS Solution:

Time Complexity: O(amount × coins.length) - similar to DP
Space Complexity: O(amount) - queue and visited set

Pattern Recognition

This problem demonstrates:

Unbounded Knapsack pattern
Minimum coins/steps optimization
Bottom-up DP technique
BFS for shortest path alternative
Foundation for many coin/change problems

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: Dynamic Programming (Bottom-Up)
5    public int coinChange(int[] coins, int amount) {
6        // Create DP array with infinity
7        int[] dp = new int[amount + 1];
8        Arrays.fill(dp, amount + 1); // Use amount+1 as "infinity"
9        dp[0] = 0; // Base case: 0 coins for amount 0
10
11        // For each amount from 1 to target
12        for (int i = 1; i <= amount; i++) {
13            // Try each coin
14            for (int coin : coins) {
15                if (coin <= i) {
16                    // Update minimum coins needed
17                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
18                }
19            }
20        }
21
22        // Return result or -1 if impossible
23        return dp[amount] > amount ? -1 : dp[amount];
24    }
25
26    // Solution 2: BFS Approach (Shortest Path)
27    public int coinChangeBFS(int[] coins, int amount) {
28        if (amount == 0) return 0;
29
30        // BFS queue: stores current amounts
31        Queue<Integer> queue = new LinkedList<>();
32        Set<Integer> visited = new HashSet<>();
33        queue.offer(0);
34        visited.add(0);
35
36        int numCoins = 0;
37
38        while (!queue.isEmpty()) {
39            int size = queue.size();
40            numCoins++;
41
42            for (int i = 0; i < size; i++) {
43                int currAmount = queue.poll();
44
45                // Try adding each coin
46                for (int coin : coins) {
47                    int nextAmount = currAmount + coin;
48
49                    // Found the target
50                    if (nextAmount == amount) {
51                        return numCoins;
52                    }
53
54                    // Continue BFS if not visited and within bounds
55                    if (nextAmount < amount && !visited.contains(nextAmount)) {
56                        visited.add(nextAmount);
57                        queue.offer(nextAmount);
58                    }
59                }
60            }
61        }
62
63        return -1; // Cannot make the amount
64    }
65
66    // Solution 3: Top-Down DP with Memoization
67    private Map<Integer, Integer> memo = new HashMap<>();
68
69    public int coinChangeMemo(int[] coins, int amount) {
70        int result = dp(coins, amount);
71        return result == Integer.MAX_VALUE ? -1 : result;
72    }
73
74    private int dp(int[] coins, int remaining) {
75        // Base cases
76        if (remaining == 0) return 0;
77        if (remaining < 0) return Integer.MAX_VALUE;
78
79        // Check memo
80        if (memo.containsKey(remaining)) {
81            return memo.get(remaining);
82        }
83
84        // Try each coin and take minimum
85        int minCoins = Integer.MAX_VALUE;
86        for (int coin : coins) {
87            int result = dp(coins, remaining - coin);
88            if (result != Integer.MAX_VALUE) {
89                minCoins = Math.min(minCoins, result + 1);
90            }
91        }
92
93        memo.put(remaining, minCoins);
94        return minCoins;
95    }
96}
97