PIXELBANKv8.2.1
Menu
Sign In

Coin Change

MediumDynamic Programming

Given coin denominations and a target amount, return the fewest coins needed. Return -1 if not possible.

Example:

Input:
1,2,5
11
Output:
3
Reasoning:
  • The target amount is 1111 and the available coin denominations are 11, 22, and 55.
  • To find the fewest coins needed, we can use a combination of the largest denomination (55) and smaller denominations to reach the target amount: 5+5+1=115 + 5 + 1 = 11.
  • This combination requires 33 coins, which is the fewest number of coins needed to reach the target amount.
  • Therefore, the output is 33, indicating that 1111 can be made with 33 coins.

Constraints:

  • 1 <= len(coins) <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
Editor

Test Results

0/0
Run code to see test results.