CodeOath
← All problems

Coin Change

Medium
dynamic-programming

Given an array of coin denominations coins and a target amount, return the fewest number of coins needed to make up amount. Each coin can be used an unlimited number of times. If that amount cannot be made up, return -1.

Example:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4