Understanding Coin Change in Java

Introduction & Problem Explanation

The Coin Change problem asks us to find the minimum number of coins needed to make up a target amount of money, using a given list of coin denominations (coins). We can assume we have an infinite supply of each kind of coin. If that amount of money cannot be made up by any combination of the coins, we should return -1.

This is a classic variation of the knapsack problem. For example, if coins = [1, 2, 5] and amount = 11, we can make 11 using 5 + 5 + 1, which requires 3 coins. This is the optimal configuration. Using a greedy strategy (always choosing the largest denomination first) fails for inputs like coins = [1, 3, 4] and amount = 6: greedy gives 4 + 1 + 1 (3 coins), whereas the optimal is 3 + 3 (2 coins). Therefore, we must evaluate all possibilities using Dynamic Programming.

The Algorithmic Approach

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

We build a table dp of size amount + 1, where dp[i] stores the minimum number of coins needed to make the value i.

• Base Case: dp[0] = 0 because 0 coins are needed to make an amount of 0.
• Initialization: We fill all other indices from 1 to amount with a placeholder representing "infinity" (we can use amount + 1, as it is impossible to need more coins than the target amount itself when the minimum denomination is at least 1).
• State Transition: For each sub-amount a from 1 to amount, we check each coin c. If a - c >= 0, then we can form a by adding one coin of value c to the optimal solution for a - c. Our transition formula is: dp[a] = Math.min(dp[a], 1 + dp[a - c]).

Finally, if dp[amount] is still greater than amount, it means no combination can form the target value, so we return -1. Otherwise, we return dp[amount].

Step-by-Step Execution Walkthrough

Let's trace the algorithm for coins = [1, 2, 5] and amount = 5:

1. Step 1 (Initialization): Declare dp array of size 6 filled with 6:
   • dp = [0, 6, 6, 6, 6, 6]
2. Step 2 (Sub-amount a = 1):
   • For coin 1: a-c = 1-1 = 0. dp[1] = Math.min(6, 1 + dp[0]) = 1.
   • For coin 2: 1-2 < 0 (skip).
   • For coin 5: 1-5 < 0 (skip).
   • State: dp = [0, 1, 6, 6, 6, 6]
3. Step 3 (Sub-amount a = 2):
   • For coin 1: 2-1 = 1. dp[2] = Math.min(6, 1 + dp[1]) = 2.
   • For coin 2: 2-2 = 0. dp[2] = Math.min(2, 1 + dp[0]) = 1.
   • For coin 5: 2-5 < 0 (skip).
   • State: dp = [0, 1, 1, 6, 6, 6]
4. Step 4 (Sub-amount a = 3):
   • For coin 1: 3-1 = 2. dp[3] = Math.min(6, 1 + dp[2]) = 2.
   • For coin 2: 3-2 = 1. dp[3] = Math.min(2, 1 + dp[1]) = 2.
   • State: dp = [0, 1, 1, 2, 6, 6]
5. Step 5 (Sub-amount a = 4):
   • For coin 1: 4-1 = 3. dp[4] = Math.min(6, 1 + dp[3]) = 3.
   • For coin 2: 4-2 = 2. dp[4] = Math.min(3, 1 + dp[2]) = 2.
   • State: dp = [0, 1, 1, 2, 2, 6]
6. Step 6 (Sub-amount a = 5):
   • For coin 1: 5-1 = 4. dp[5] = Math.min(6, 1 + dp[4]) = 3.
   • For coin 2: 5-2 = 3. dp[5] = Math.min(3, 1 + dp[3]) = 3.
   • For coin 5: 5-5 = 0. dp[5] = Math.min(3, 1 + dp[0]) = 1.
   • State: dp = [0, 1, 1, 2, 2, 1]
7. Step 7 (Result): dp[5] = 1. This is returned.

Key Code Snippets & 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 - c >= 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 - c]);: 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

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

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

The Coin Change problem shows why greedy search isn't always optimal. By adopting a dynamic programming approach, we systematically check all configurations in a bottom-up fashion, achieving a highly optimized linear O(n * amount) runtime.