# 1. Introduction

The "Coin Change" problem is a classic example of dynamic programming and combinatorics. It involves determining the minimum number of coins required to make up a given amount of money using coins of specified denominations. This problem is a staple in algorithm design for learning about optimization and dynamic programming techniques.

## Problem

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

# 2. Solution Steps

1. Initialize a dynamic programming array *dp* with size *amount + 1* and fill it with a large number (e.g., *amount + 1*).

2. Set the base case *dp[0] = 0* since no coins are needed for the amount 0.

3. Iterate through each amount from 1 to *amount*.

4. For each amount, iterate through the coin denominations and update the *dp* array.

5. The *dp* value for an amount is the minimum of its current value and one more than the *dp* value for the amount minus the current coin's denomination.

6. After filling the *dp* array, check if the *amount* is achievable (i.e., *dp[amount] != amount + 1*).

7. Return the value of *dp[amount]* if achievable; otherwise, return -1.

# 3. Code Program

```
def coinChange(coins, amount):
MAX = amount + 1
dp = [MAX] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for coin in coins:
if a - coin >= 0:
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != MAX else -1
# Example Usage
print(coinChange([1, 2, 5], 11))
print(coinChange([2], 3))
print(coinChange([1], 0))
```

### Output:

3 -1 0

### Explanation:

**1. Dynamic Programming Array**: *dp* holds the minimum number of coins needed for each amount up to *amount*.

**2. Base Case**: *dp[0]* is 0 since no coins are required to make the amount 0.

**3. Iterative Calculation**: For each amount, the function calculates the minimum number of coins by considering each coin denomination.

**4. Minimum Coin Count**: The minimum number of coins for an amount is updated by checking if using a coin reduces the total count.

**5. Final Check**: After computing, the function checks if the amount is achievable by comparing *dp[amount]* with *MAX*.

**6. Result**: The function returns the minimum number of coins needed if achievable, else returns -1.

## Comments

## Post a Comment