Coin Change — Minimum Coins
Practice this coding question on Coding Gurukul.
Problem statement
Given coin denominations and a target amount, find the minimum number of coins needed to make exactly that amount. You may use each denomination any number of times. Print -1 if the amount cannot be made. A target of 0 needs 0 coins. Repeated denominations do not change the answer. Use dynamic programming in O(n*target) time and O(target) space. Choosing the largest coin first is not always optimal. Worked example For coins [1, 3, 4] and target 6, use 3+3. The answer is 2. Using 4+1+1 would require 3 coins.
Input format
First line: n target. Second line: n denominations.
Output format
Print the minimum coin count, or -1.
Constraints
1 <= n <= 100; 0 <= target <= 10000; 1 <= denomination <= 10000.
Sample input
3 6 1 3 4
Sample output
2
Sign in to run or submit a solution in C++, Java or Python.