All problems

Coin Change

Medium · dynamic programming

You have coins of several denominations in coins, and as many copies of each denomination as you want. Given a target amount of money, return the fewest coins that add up to exactly amount.

If no combination of coins can make that amount, return -1. An amount of 0 needs no coins, so the answer there is 0.

Examples

Example 1

Input: coins = [1, 2, 5], amount = 11

Output: 3

5 + 5 + 1 = 11 uses three coins, and no two coins can make 11.

Example 2

Input: coins = [2], amount = 3

Output: -1

Every sum of 2s is even, so 3 can never be reached.

Example 3

Input: coins = [1, 3, 4], amount = 6

Output: 2

3 + 3 = 6. Taking the biggest coin first (4 + 1 + 1) would use three coins.

Constraints