5. Coin Change
MediumDynamic Programming
Given coin denominations (unlimited supply of each) and an amount, print the fewest coins needed to make that amount, or -1 if it cannot be made.
Input format
Line 1: k (number of denominations) Line 2: k coin values Line 3: amount
Output format
Minimum number of coins, or -1.
Example 1
Input
3 1 2 5 11
Output
3
Explanation: 11 = 5 + 5 + 1.
Example 2
Input
1 2 3
Output
-1
Explanation: 3 cannot be made from 2s.
Constraints
1 ≤ k ≤ 12 1 ≤ coin ≤ 2³¹ − 1 0 ≤ amount ≤ 10⁴
Read input from standard input and print the answer to standard output. Your code is judged against 6 test cases, most of them hidden.
Loading the MyLoginn IDE…