Coin Change Problem

//Coin Change Problem 

import java.util.*;

public class CoinChange {

    // Memoization array to store results for subproblems
    private static int[] memo;

    public static int coinChange(int[] coins, int amount) {
        // Initialize memo array with -2 (indicates uncalculated)
        memo = new int[amount + 1];
        Arrays.fill(memo, -2);

        // Call recursive helper function
        int result = helper(coins, amount);

        // If result is a large number, return -1 (not possible)
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    // Recursive helper function to find min coins for current amount
    private static int helper(int[] coins, int amount) {
        // Base case: if amount is 0, no coins needed
        if (amount == 0) return 0;

        // Base case: negative amount means no solution
        if (amount < 0) return Integer.MAX_VALUE;

        // Return cached result if already computed
        if (memo[amount] != -2) return memo[amount];

        int minCoins = Integer.MAX_VALUE;

        // Try every coin and choose the one with minimum coins
        for (int coin : coins) {
            int res = helper(coins, amount - coin);
            if (res != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, res + 1);
            }
        }

        // Store the computed result in memo and return
        memo[amount] = minCoins;
        return minCoins;
    }

    // Main method to test the code
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;

        int result = coinChange(coins, amount);
        if (result == -1) {
            System.out.println("It is not possible to make the amount with given coins.");
        } else {
            System.out.println("Minimum coins needed: " + result);
        }
    }
}