60. Coin Change

Medium · Dynamic Programming

You are given an integer array `coins` representing coin denominations and an integer `amount` representing a target amount of money. Return the fewest number of coins needed to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Each coin in the array can be used an unlimited number of times.

Examples

Example 1
Input: coins = [1, 2, 5], amount = 5
Output: 1
Explanation: 5 = 5 (one coin of denomination 5)
Example 2
Input: coins = [2], amount = 3
Output: -1
Explanation: The amount 3 cannot be made with only coins of denomination 2

Constraints