Understanding Coin Change in Java

Optimizing resource allocation is a core challenge in computer science, and the Coin Change problem is one of its most famous representations. In this puzzle, you are given an array of coin denominations (such as $1, $2, and $5) and a target amount of money. Your task is to calculate the minimum number of coins required to make up that exact amount. If it's impossible to form the target amount with the given coins, you should return -1. We assume that we have an infinite supply of each coin denomination.

At first glance, a greedy strategy seems like the obvious choice: simply pick the largest coin value that fits, subtract it, and repeat. While this works for standard currency systems (like US dollars), it fails on custom coin systems. For instance, if your coins are [1, 3, 4] and you need to make 6, a greedy approach would pick 4, leaving you with two 1s (totaling 3 coins: 4 + 1 + 1). However, the optimal solution is actually two 3-value coins (3 + 3 = 6), which only takes 2 coins. Because greedy choices can lead to sub-optimal outcomes, we must use dynamic programming to check all options efficiently.

Solving the Problem

Bottom-Up Dynamic Programming (O(n * amount) Time, O(amount) Space)

To solve this problem systematically, we construct a table dp of size amount + 1, where each index i represents the minimum coins needed to make the value i.

• Base Case: We set dp[0] = 0 because it takes zero coins to make an amount of zero.
• Initialization: We fill all other indices from 1 to amount with a sentinel value representing infinity (e.g., amount + 1), indicating that these values are currently unreachable.
• State Transition: For each sub-amount a from 1 to amount, we evaluate each coin denomination c. If a - c >= 0, we check if using coin c gives us a better count. Our update formula is: dp[a] = Math.min(dp[a], 1 + dp[a - c]).

Once the table is filled, if dp[amount] remains greater than amount, we know the target is unreachable and return -1. Otherwise, we return the calculated minimum value.

Tracing the Logic

Let's trace this logic for coins = [1, 2, 5] and a target amount = 5:

1. Start: dp is initialized to [0, 6, 6, 6, 6, 6].
2. Amount 1: The only coin that fits is 1. We calculate dp[1] = Math.min(6, 1 + dp[0]) = 1.
3. Amount 2: We can use coin 1 (gives 1 + dp[1] = 2) or coin 2 (gives 1 + dp[0] = 1). We pick the minimum, so dp[2] = 1.
4. Amount 3: Using coin 1 gives 1 + dp[2] = 2. Using coin 2 gives 1 + dp[1] = 2. Thus, dp[3] = 2.
5. Amount 4: Using coin 1 gives 1 + dp[3] = 3. Using coin 2 gives 1 + dp[2] = 2. Thus, dp[4] = 2.
6. Amount 5: We evaluate all three coins: coin 1 (gives 1 + dp[4] = 3), coin 2 (gives 1 + dp[3] = 3), or coin 5 (gives 1 + dp[0] = 1). The minimum is 1, so dp[5] = 1.

The final answer is 1 (since we have a single $5 coin).

Key Explanations

Here is why the main logic in the solution is important:

• Arrays.fill(dp, amount + 1);: Uses a logical equivalent to infinity that fits in standard integer values and avoids overflow errors (which would occur if we used Integer.MAX_VALUE and then added 1 to it).
• if (a - coin >= 0): Ensures we only attempt to construct target amounts using coin denominations that are less than or equal to the target value.
• Math.min(dp[a], 1 + dp[a - coin]);: Compares our current best coin count for amount a with the option of using coin c, choosing the path with fewer coins.

Java Implementation Code

Here is the complete Java code showing this bottom-up dynamic programming approach. The code initializes the table and iterates through all possible sub-amounts, checking each coin denomination dynamically.

package io.practise.dsa;

import java.util.Arrays;

public class CoinChange {

    // Bottom-Up Dynamic Programming: Time O(N * Amount), Space O(Amount)
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }

        int[] dp = new int[amount + 1];
        // Fill with a sentinel value representing infinity
        Arrays.fill(dp, amount + 1);
        dp[0] = 0; // Base case: 0 amount needs 0 coins

        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (a - coin >= 0) {
                    dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
                }
            }
        }

        // If the target amount remains set to infinity, it cannot be reached
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        CoinChange solver = new CoinChange();
        int[] coins = {1, 2, 5};
        int amount = 11;

        System.out.println("--- Coin Change Demonstration ---");
        System.out.println("Available Coins: " + Arrays.toString(coins));
        System.out.println("Target Amount: " + amount);
        int result = solver.coinChange(coins, amount);
        System.out.println("Minimum coins required: " + result); // Expected: 3 (5 + 5 + 1)
    }
}

Conclusion & Complexity Analysis

This bottom-up approach runs in O(N * amount) time, where N is the number of coin denominations, and uses O(amount) auxiliary space. By avoiding the pitfalls of a pure greedy search, this dynamic programming approach guarantees we find the mathematically optimal solution for any set of coin values.