Array String Dynamic Programming Memoization Tabulation
Proficient Level

Implement the coinChangeMinimumCoins method that returns the minimum number of coins needed to make the amount.

The input contains coin denominations coins, their count size, and a target amount.

Your task is to return the minimum number of coins needed to make exactly that amount. You may use each coin denomination multiple times.

If the amount cannot be formed using the given coins, return -1. For example, with coins [1,2,5] and amount 11, the minimum number of coins is 3 using 5 + 5 + 1.

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]
size (int) = 1
amount (int) = 0
Return:
(int) 0

Use dynamic programming where dp[x] stores the minimum coins required to form amount x.

Start with dp[0] = 0 because zero coins are required to form amount zero. For every amount, try every coin. If the coin can be used, update the answer from the smaller amount amount - coin.

After filling the table, if the target amount still has a large impossible value, return -1.

Pseudocode:

function coinChangeMinimumCoins(coins, size, amount):
    dp = array of amount + 1 filled with infinity
    dp[0] = 0
    for value from 1 to amount:
        for each coin in coins:
            if coin <= value:
                dp[value] = min(dp[value], dp[value - coin] + 1)
    if dp[amount] is infinity:
        return -1
    return dp[amount]
Run your code to see the result.