Array Math Dynamic Programming Tabulation
Proficient Level

Implement the minimumCoinsToMakeAmount method that finds the minimum number of coins required to make the target 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 the target amount.

You may use each coin denomination any number of times. If it is not possible to make the amount, return -1. For example, with coins [1,2,5] and amount 11, the minimum is 3 coins: 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 to store the fewest coins needed for every amount from 0 to the target.

Set dp[0] = 0 because zero coins are needed to make amount zero. All other positions can start with a large value, meaning they are not reachable yet.

For every amount, try each coin. If the coin can be used, update the answer with 1 + dp[amount - coin]. At the end, return -1 if the target amount is still unreachable.

Pseudocode:

function minimumCoinsToMakeAmount(coins, size, amount):
    dp = array of amount + 1 values filled with infinity
    dp[0] = 0
    for value from 1 to amount:
        for each coin in coins:
            if coin <= value and dp[value - coin] is not infinity:
                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.