Given an integer array representing coin denominattions and a target amount, determine the minimum number of coins required to make up that amount. Return -1 if no valid combination exists. Coins can be used unlimited times.

Recursive Approach

A recursive function findMinCoins(int[] denominations, int target) calculates the minimum coins needed for a given amount. For each coin denomination, the function recursively computes the solution for target - denomination and selects the minimum count.

public static int minCoins(int[] denominations, int target) {
    return findMinCoins(denominations, target);
}

private static int findMinCoins(int[] denominations, int remaining) {
    if (remaining < 0) return -1;
    if (remaining == 0) return 0;
    
    int minimum = Integer.MAX_VALUE;
    for (int denomination : denominations) {
        int result = findMinCoins(denominations, remaining - denomination);
        if (result == -1) continue;
        minimum = Math.min(minimum, result + 1);
    }
    return minimum == Integer.MAX_VALUE ? -1 : minimum;
}

Dynamic Programming Solution

Convert the recursive solution to dynamic programming using a DP array where dp[i] represents the minimum coins for amount i. The solution builds from smaller amounts to the target.

public static int minCoinsDP(int[] denominations, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 0;
    int currentMin = Integer.MAX_VALUE;
    
    for (int currentAmount = 1; currentAmount <= target; currentAmount++) {
        for (int denomination : denominations) {
            int previous = getDPValue(dp, currentAmount - denomination);
            if (previous == -1) continue;
            currentMin = Math.min(currentMin, previous + 1);
        }
        dp[currentAmount] = currentMin == Integer.MAX_VALUE ? -1 : currentMin;
        currentMin = Integer.MAX_VALUE;
    }
    return dp[target];
}

private static int getDPValue(int[] dp, int index) {
    if (index < 0) return -1;
    return dp[index];
}

Optimized Dynamic Programming

Initialize the DP array with a large value and update only when coin denomination is valid. Early termination occurs when coin value exceeds current amount.

public int minCoinsOptimized(int[] denominations, int target) {
    int[] dp = new int[target + 1];
    Arrays.fill(dp, target + 1);
    dp[0] = 0;
    
    for (int currentAmount = 1; currentAmount <= target; currentAmount++) {
        for (int denomination : denominations) {
            if (denomination <= currentAmount) {
                dp[currentAmount] = Math.min(dp[currentAmount], dp[currentAmount - denomination] + 1);
            }
        }
    }
    return dp[target] > target ? -1 : dp[target];
}