DynamicCoinChangeSolver.cs

usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;

namespaceAlgorithms.Problems.DynamicProgramming.CoinChange;

publicstaticclassDynamicCoinChangeSolver
{
/// <summary>
/// Generates an array of changes for current coin.
/// For instance, having coin C = 6 and array A = [1,3,4] it returns an array R = [2,3,5].
/// Because, 6 - 4 = 2, 6 - 3 = 3, 6 - 1 = 5.
/// </summary>
/// <param name="coin">The value of the coin to be exchanged.</param>
/// <param name="coins">An array of available coins.</param>
/// <returns>Array of changes of current coins by available coins.</returns>
publicstaticint[]GenerateSingleCoinChanges(intcoin,int[]coins)
{
ValidateCoin(coin);
ValidateCoinsArray(coins);

varcoinsArrayCopy=newint[coins.Length];

Array.Copy(coins,coinsArrayCopy,coins.Length);
Array.Sort(coinsArrayCopy);
Array.Reverse(coinsArrayCopy);

varlist=newList<int>();

foreach(varitemincoinsArrayCopy)
{
if(item>coin)
{
continue;
}

vardifference=coin-item;

list.Add(difference);
}

varresult=list.ToArray();

returnresult;
}

/// <summary>
/// Given a positive integer N, such as coin.
/// Generates a change dictionary for all values [1,N].
/// Used in so-called backward induction in search of the minimum exchange.
/// </summary>
/// <param name="coin">The value of coin.</param>
/// <param name="coins">Array of available coins.</param>
/// <returns>Change dictionary for all values [1,N], where N is the coin.</returns>
publicstaticDictionary<int,int[]>GenerateChangesDictionary(intcoin,int[]coins)
{
vardict=newDictionary<int,int[]>();
varcurrentCoin=1;

while(currentCoin<=coin)
{
varchangeArray=GenerateSingleCoinChanges(currentCoin,coins);
dict[currentCoin]=changeArray;
currentCoin++;
}

returndict;
}

/// <summary>
/// Gets a next coin value, such that changes array contains the minimal change overall possible changes.
/// For example, having coin N = 6 and A = [1,3,4] coins array.
/// The minimum next coin for 6 will be 3, because changes of 3 by A = [1,3,4] contains 0, the minimal change.
/// </summary>
/// <param name="coin">Coin to be exchanged.</param>
/// <param name="exchanges">Dictionary of exchanges for [1, coin].</param>
/// <returns>Index of the next coin with minimal exchange.</returns>
publicstaticintGetMinimalNextCoin(intcoin,Dictionary<int,int[]>exchanges)
{
varnextCoin=int.MaxValue;
varminChange=int.MaxValue;

varcoinChanges=exchanges[coin];

foreach(varchangeincoinChanges)
{
if(change==0)
{
return0;
}

varcurrentChange=exchanges[change];
varmin=currentChange.Min();

varminIsLesser=min<minChange;

if(minIsLesser)
{
nextCoin=change;
minChange=min;
}
}

returnnextCoin;
}

/// <summary>
/// Performs a coin change such that an amount of coins is minimal.
/// </summary>
/// <param name="coin">The value of coin to be exchanged.</param>
/// <param name="coins">An array of available coins.</param>
/// <returns>Array of exchanges.</returns>
publicstaticint[]MakeCoinChangeDynamic(intcoin,int[]coins)
{
varchangesTable=GenerateChangesDictionary(coin,coins);
varlist=newList<int>();

varcurrentCoin=coin;
varnextCoin=int.MaxValue;

while(nextCoin!=0)
{
nextCoin=GetMinimalNextCoin(currentCoin,changesTable);
vardifference=currentCoin-nextCoin;
list.Add(difference);
currentCoin=nextCoin;
}

varresult=list.ToArray();

returnresult;
}

privatestaticvoidValidateCoin(intcoin)
{
if(coin<=0)
{
thrownewInvalidOperationException($"The coin cannot be lesser or equal to zero {nameof(coin)}.");
}
}

privatestaticvoidValidateCoinsArray(int[]coinsArray)
{
varcoinsAsArray=coinsArray.ToArray();

if(coinsAsArray.Length==0)
{
thrownewInvalidOperationException($"Coins array cannot be empty {nameof(coinsAsArray)}.");
}

varcoinsContainOne=coinsAsArray.Any(x =>x==1);

if(!coinsContainOne)
{
thrownewInvalidOperationException($"Coins array must contain coin 1 {nameof(coinsAsArray)}.");
}

varcontainsNonPositive=coinsAsArray.Any(x =>x<=0);

if(containsNonPositive)
{
thrownewInvalidOperationException(
$"{nameof(coinsAsArray)} cannot contain numbers less than or equal to zero");
}

varcontainsDuplicates=coinsAsArray.GroupBy(x =>x).Any(g =>g.Count()>1);

if(containsDuplicates)
{
thrownewInvalidOperationException($"Coins array cannot contain duplicates {nameof(coinsAsArray)}.");
}
}
}