using System;

public class Program

{

    public static int ChangePossibilitiesBottomUp(int goal, int[] denominations)

    {

        int[] waysOfDoingNCents = new int[goal +1];

        waysOfDoingNCents[0] = 1;

        foreach(int coin in denominations) {

            for(int higherAmount = coin; higherAmount <= goal; higherAmount++) {

                int higherAmountRemainder = higherAmount - coin;

                waysOfDoingNCents[higherAmount] += waysOfDoingNCents[higherAmountRemainder];

            }

        }

        // Write the body of your function here

        return waysOfDoingNCents[goal];

    }

    public static void Main()

    {

        // Run your function through some test cases here.

        // Remember: debugging is half the battle!

        int[] denominations = {1, 2, 3};

        Console.WriteLine(ChangePossibilitiesBottomUp(4, denominations)); // Expected 4.

        int[] denoms2 = {1, 3, 5};

        Console.WriteLine(ChangePossibilitiesBottomUp(5, denoms2));

    }

}