The Change Machine

The Currency Combiner (Coin Change)

Imagine you are at a futuristic vending machine. You need to provide exactly a certain amount of change using the fewest possible coins. You have an infinite supply of specific denominations. This is a classic "Optimization" problem where small decisions (which coin to use) build up to the best overall result.

The Assignment

Your mission is to find the minimum number of coins. Your function receives coins (array of denominations) and an amount.

1. Create a dp array of size amount + 1 filled with a "Large Number" (Infinity).
2. Set dp[0] = 0 (It costs 0 coins to make $0).
3. For each amount from 1 to target:
   • Check every coin: If the coin value is less than or equal to the current amount, update dp[i] = min(dp[i], dp[i - coin] + 1).
4. If dp[amount] is still the "Large Number," print -1. Otherwise, print the value.