Coin Change

public class Solution {
  public int minCoins(int[] currency, int total) {
    int upperBound = total + 1;
    int[] dpTable = new int[total + 1];
    Arrays.fill(dpTable, upperBound);
    dpTable[0] = 0;
    for (int i = 1; i <= total; i++) {
      for (int c = 0; c < currency.length; c++) {
        if (currency[c] <= i) {
          dpTable[i] = Math.min(dpTable[i], dpTable[i - currency[c]] + 1);
        }
      }
    }
    return dpTable[total] > total ? -1 : dpTable[total];
  }
}

The Java solution provided computes the minimum number of coins needed to make up a given amount, using the classical dynamic programming approach. The method, minCoins, accepts two parameters: an array currency containing the denominations of the coins available, and an integer total, which is the amount for which we need to find the minimum number of coins.

Here’s a concise breakdown of how the algorithm is structured:

• Initializes an array dpTable of size total + 1 to store the minimum number of coins needed for each sub-amount from 0 to total. It fills this array with a value greater than any possible number of coins needed (upperBound), except for the first element, dpTable[0], which is set to 0 because no coins are needed to make an amount of 0.

• Iterates over each sub-amount from 1 to total and for each denomination available in the currency array. If the denomination is less than or equal to the sub-amount i, it updates dpTable[i] to be the minimum of its current value and the value of dpTable[i - currency[c]] + 1.

• Finally, it checks if the value at dpTable[total] is still greater than total (the initialized upperBound). If so, it means it is not possible to form the amount with the given coins, and it returns -1. Otherwise, it returns the value of dpTable[total], which represents the minimum number of coins.

This solution ensures efficient computation by avoiding unnecessary recalculations and by systematically building up the solution through the dpTable.

class Solution:
    def getMinCoins(self, denominations: List[int], total: int) -> int:
        cache = [float('inf')] * (total + 1)
        cache[0] = 0

        for denomination in denominations:
            for i in range(denomination, total + 1):
                cache[i] = min(cache[i], cache[i - denomination] + 1)
        return cache[total] if cache[total] != float('inf') else -1

The Coin Change algorithm in Python3 involves determining the minimum number of coins needed to make up a specific amount using given denominations. Here's how the solution works:

• Initialize a list cache where cache[i] represents the minimum number of coins needed to achieve the value i. Initially, set all values in this list to infinity (float('inf')), except for cache[0] which is 0 because no coins are needed to make up the amount 0.

• Loop through each coin denomination. For each denomination, iterate through possible totals from the denomination value up to the desired total. Update the cache list by comparing the existing value with the new possible minimum number of coins needed (either keep it the same or take the denomination and add one to the number of coins needed to make up the total minus the denomination).

• Finally, if cache[total] holds a value other than infinity, it contains the minimum number of coins required for the given total, otherwise return -1, signaling that it's not possible to sum to the total with the provided denominations.

This dynamic programming approach ensures that each sub-problem is solved efficiently and results can be reused, leading to an overall efficient solution for the minimum coin change problem.