Math Dynamic Programming
Proficient Level

Implement the method coinChangeMinCoins that returns the minimum number of coins needed for an amount.

You may use each coin value any number of times. Return the fewest coins needed to make the target amount exactly.

The task is designed to test careful handling of edge cases, not only the most common input.

  • Use only the first size coin values.
  • Return 0 when the amount is 0.
  • Return -1 when the amount cannot be formed.
Example 1
Input:
coins (int[]) = [1,2,5]
size (int) = 3
amount (int) = 11
Return:
(int) 3
Example 2
Input:
coins (int[]) = [2]
size (int) = 1
amount (int) = 3
Return:
(int) -1
Example 3
Input:
coins (int[]) = [1,3,4]
size (int) = 3
amount (int) = 6
Return:
(int) 2

Use dynamic programming where dp[x] stores the fewest coins needed for amount x.

Run your code to see the result.