#### Dynamic

```﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Problems.CoinChange
{
public static class DynamicCoinChangeSolver
{
/// <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>
public static int[] GenerateSingleCoinChanges(int coin, int[] coins)
{
ValidateCoin(coin);
ValidateCoinsArray(coins);

var coinsArrayCopy = new int[coins.Length];

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

var list = new List<int>();

foreach (var item in coinsArrayCopy)
{
if (item > coin)
{
continue;
}

var difference = coin - item;

}

var result = list.ToArray();

return result;
}

/// <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>
public static Dictionary<int, int[]> GenerateChangesDictionary(int coin, int[] coins)
{
var dict = new Dictionary<int, int[]>();
var currentCoin = 1;

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

return dict;
}

/// <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>
public static int GetMinimalNextCoin(int coin, Dictionary<int, int[]> exchanges)
{
var nextCoin = int.MaxValue;
var minChange = int.MaxValue;

var coinChanges = exchanges[coin];

foreach (var change in coinChanges)
{
if (change == 0)
{
return 0;
}

var currentChange = exchanges[change];
var min = currentChange.Min();

var minIsLesser = min < minChange;

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

return nextCoin;
}

/// <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>
public static int[] MakeCoinChangeDynamic(int coin, int[] coins)
{
var changesTable = GenerateChangesDictionary(coin, coins);
var list = new List<int>();

var currentCoin = coin;
var nextCoin = int.MaxValue;

while (nextCoin != 0)
{
nextCoin = GetMinimalNextCoin(currentCoin, changesTable);
var difference = currentCoin - nextCoin;
currentCoin = nextCoin;
}

var result = list.ToArray();

return result;
}

private static void ValidateCoin(int coin)
{
if (coin <= 0)
{
throw new InvalidOperationException(\$"The coin cannot be lesser or equal to zero {nameof(coin)}.");
}
}

private static void ValidateCoinsArray(int[] coinsArray)
{
var coinsAsArray = coinsArray.ToArray();

if (coinsAsArray.Length == 0)
{
throw new InvalidOperationException(\$"Coins array cannot be empty {nameof(coinsAsArray)}.");
}

var coinsContainOne = coinsAsArray.Any(x => x == 1);

if (!coinsContainOne)
{
throw new InvalidOperationException(\$"Coins array must contain coin 1 {nameof(coinsAsArray)}.");
}

var containsNonPositive = coinsAsArray.Any(x => x <= 0);

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

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

if (containsDuplicates)
{
throw new InvalidOperationException(\$"Coins array cannot contain duplicates {nameof(coinsAsArray)}.");
}
}
}
}
```