using System;

​

public int MinNumberOfCoinsForChange(int n, int[] denoms)

{

    int toCompare = 0;

    int[] numOfCoins = new int[n + 1];

    numOfCoins = FillArrayMax(numOfCoins);

    numOfCoins[0] = 0;

    foreach (int denom in denoms)

    {

        for (int amount = 0; amount < numOfCoins.Length; amount++)

        {

            if (denom <= amount)

            {

                if (numOfCoins[amount - denom] == Int32.MaxValue)

                    toCompare = numOfCoins[amount - denom];

                else

                    toCompare = numOfCoins[amount - denom] + 1;

                numOfCoins[amount] = Math.Min(numOfCoins[amount], toCompare);

            }

        }

    }

​

    return numOfCoins[n] != Int32.MaxValue ? numOfCoins[n] : -1;

}

​

public int[] FillArrayMax(int[] array)

{

    for (int i = 0; i < array.Length; i++)

        array[i] = Int32.MaxValue;

    return array;

}

​

private void Test()

{

    Console.WriteLine("Expecting: 3 |  Actual: " + MinNumberOfCoinsForChange(7, new int[]{1, 5, 10}));

    Console.WriteLine("Expecting: 3 |  Actual: " + MinNumberOfCoinsForChange(7, new int[]{1, 10, 5}));

    Console.WriteLine("Expecting: 0 |  Actual: " + MinNumberOfCoinsForChange(0, new int[]{1, 2, 3}));

    Console.WriteLine("Expecting: 2 |  Actual: " + MinNumberOfCoinsForChange(3, new int[]{2, 1}));

    Console.WriteLine("Expecting: 3 |  Actual: " + MinNumberOfCoinsForChange(135, new int[]{39, 1, 45, 130, 40, 4, 1}));

}

​

Test();