# 1. Introduction

In this post, we tackle the "Coin Change" problem, a fundamental problem in dynamic programming. The challenge involves finding the minimum number of coins needed to make up a specific amount of money, given coins of different denominations. This problem is a classic example of making optimal choices to reach a desired outcome.

## Problem

Given an array *coins* representing different coin denominations and an integer *amount* representing a total amount of money, the task is to determine the fewest number of coins needed to make up that amount. If it is not possible to make up the amount with the given coins, return -1. It is assumed that there is an infinite supply of each coin denomination.

# 2. Solution Steps

1. Use dynamic programming to solve the problem.

2. Create an array *dp* of size *amount + 1* to store the minimum number of coins needed for each amount from 0 to *amount*.

3. Initialize each element in *dp* to a maximum value, and set *dp[0]* to 0.

4. Iterate through each coin, and for each coin, update the *dp* array for all amounts that can be reached using that coin.

5. For each amount *i*, if *i - coin* is reachable, update *dp[i]* to the minimum of its current value and *dp[i - coin] + 1*.

6. After processing all coins, if *dp[amount]* is still at its maximum value, return -1, otherwise, return *dp[amount]*.

# 3. Code Program

```
public class CoinChange {
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int amount = 11;
System.out.println(coinChange(coins, amount)); // Test the function
}
// Function to find the fewest number of coins needed to make up the amount
public static int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[max];
Arrays.fill(dp, max);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
```

### Output:

3

### Explanation:

1. *coinChange*: This function computes the minimum number of coins required to make up a given *amount* using coins of various denominations.

2. It initializes a dynamic programming array *dp*, where *dp[i]* represents the minimum number of coins needed to make up amount *i*.

3. The function iterates over each coin and updates *dp[i]* for all amounts that can be made using that coin. This is done by checking if the current amount minus the coin value is reachable and, if so, updating the minimum number of coins needed.

4. After processing, if *dp[amount]* is still at its initialized maximum value, it means the amount cannot be made up with the given coins, and the function returns -1. Otherwise, it returns the value of *dp[amount]*.

5. This approach ensures that the problem is solved optimally by iteratively building up the solution for each amount, considering each coin denomination.

## Comments

## Post a Comment