Fewest coins
Given coin values (unlimited coins of each) and an amount, print the smallest number of coins that make the amount exactly. If it cannot be made, print -1.
Reported in: Infosys (DSE / SP, 2021–26) (memory-based)
Input
Line 1: N (number of coin values). Line 2: the N coin values. Line 3: the amount.
Output
The fewest coins, or -1.
Constraints
1 ≤ N ≤ 100; 0 ≤ amount ≤ 10^4.
Example 1
Input:
3
1 2 5
11
Output:
3Example 2
Input:
1
2
3
Output:
-1Hint: dp[x] = 1 + min(dp[x − coin]) over all coins, with dp[0] = 0.