Implement the Coin Change problem (minimum number of coins) using dynamic programming.?

The Coin Change problem is a classic problem in computer science and can be solved using dynamic programming. The problem statement is as follows:

Given a set of coins and a target amount, find the minimum number of coins required to make up the target amount. Assume that there are unlimited coins of each denomination.

For example, if the input is coins = [1, 5, 10, 25] and the target amount is 36, the minimum number of coins required is 3 (one quarter and two dimes).

To solve this problem using dynamic programming, we can use a bottom-up approach where we build a table to keep track of the minimum number of coins required for each target amount.

Let’s begin with declaring an array or a map that will hold the minimum number of coins required for each target value. We can initialize the array with maxValue value for all target values except for zero, which requires zero coins to make up.

int[] minCoins = new int[target + 1];
Arrays.fill(minCoins, Integer.MAX_VALUE);
minCoins[0] = 0;

Next, we can iterate through all possible target values and for each target value, we can iterate through all the available coins. We can use the following recurrence relation to compute the minimum number of coins required for a particular target value:

minCoins[target] = min(minCoins[target], 1 + minCoins[target - coin])

The above formula means that the minimum number of coins required to make up the target value is the minimum of the previous minimum required coins for that target value or 1 added to the minimum number of coins required to make up the difference between the target value and the coin denomination.

Here is the complete implementation of the dynamic programming solution:

public int coinChange(int[] coins, int amount) {
    int[] minCoins = new int[amount + 1];
    Arrays.fill(minCoins, Integer.MAX_VALUE);
    minCoins[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && minCoins[i - coin] != Integer.MAX_VALUE) {
                minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i - coin]);
            }
        }
    }
    
    return minCoins[amount] == Integer.MAX_VALUE ? -1 : minCoins[amount];
}

The time complexity of this solution is O(amount * number of coins) and the space complexity is O(amount).