Problem Statement

Given a integer array coins representing different coin denominations and an integer amount representing the target total, find the minimum number of coins needed to make up that amount. If it's impossible to form the amount with the given coins, return -1.

You have an unlimited supply of each coin denomination.

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

Approach

This is a classic dynamic programming problem. The key insight is that to compute the minimum coins for amount i, we need to consider all possible last coins we could use.

Define dp[i] as the minimum number of coins required to make amount i. For each amount, we iterate through all available coins and check if using a particular coin leads to a better solution.

The recurrence relation is:

dp[i] = min(dp[i], dp[i - coin] + 1) for each valid coin

Important Implemantation Details

• Initialize the dp array with amount + 1 instead of Integer.MAX_VALUE. Using MAX_VALUE can cause integer overflow when adding 1 during the dp[i - coin] + 1 calculation.
• Set dp[0] = 0 since zero coins are needed to make amount zero.
• After processing all amounts, if dp[amount] remains amount + 1, it means the amount cannot be formed.

Soluiton

class Solution {
    public int coinChange(int[] coins, int amount) {
        // Initialize dp array with a sentinel value greater than any possible answer
        int INF = amount + 1;
        int[] dp = new int[amount + 1];
        
        // Fill dp array with sentinel value
        Arrays.fill(dp, INF);
        
        // Base case: 0 coins needed for amount 0
        dp[0] = 0;
        
        // Fill dp table bottom-up
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // Return result if valid, otherwise -1
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

Complexity Analysis

• Time Complexity: O(amount × n) where n is the number of coin denominations
• Space Complexity: O(amount) for the dp array

Alternative: BFS Approach

This problem can also be solved using Breadth-First Search by treating each amount as a node and exploring reachable amounts by adding coins. The first time we reach the target amount gives us the minimum number of coins.

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[amount + 1];
        
        queue.offer(0);
        visited[0] = true;
        int step = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            
            for (int i = 0; i < size; i++) {
                int current = queue.poll();
                
                for (int coin : coins) {
                    int next = current + coin;
                    
                    if (next == amount) {
                        return step;
                    }
                    
                    if (next < amount && !visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
        }
        
        return -1;
    }
}