112. Coin Change - Minimum Coins

You're building a payment system that needs to calculate the minimum number of coins needed to make change. This is useful for cash registers, vending machines, or any system that needs to optimize coin usage.

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Requirements

1. Basic Functionality

• Find minimum number of coins to make amount
• Use coins of given denominations
• Return -1 if amount cannot be made
• Infinite supply of each coin

Example Usage

coinChange([1, 2, 5], 11); // 3
// Explanation: 11 = 5 + 5 + 1

coinChange([2], 3); // -1
// Explanation: Cannot make 3 with coins of value 2

coinChange([1], 0); // 0
// Explanation: 0 coins needed for amount 0

Real-World Context

This problem models real payment scenarios:

• Cash registers: Calculate minimum coins for change
• Vending machines: Optimize coin dispensation
• Payment systems: Minimize transaction costs
• Dynamic programming: Classic DP problem