class CoinChangeCount
{
    static void Main(string[] args)
    {
        int[] coins = { 1, 10, 50, 100 };            

        CoinChangeCount c = new CoinChangeCount();
        int ans = c.Count(coins, 4, 90);
        Console.WriteLine("Count={0}", ans);
        
        Dictionary<Tuple<int, int>, int> hash = new Dictionary<Tuple<int, int>, int>();
        ans = c.DPCount(coins, 4, 90, hash);
        Console.WriteLine("Count={0}", ans);
    }

    int Count(int[] coins, int m, int n)
    {
        if (n == 0) return 1;
        if (n < 0) return 0;
        if (m <= 0) return 0;

        return Count(coins, m - 1, n) + Count(coins, m, n - coins[m - 1]);
    }

    int DPCount(int[] coins, int m, int n, Dictionary<Tuple<int, int>, int> hash)
    {
        if (n == 0) return 1;
        if (n < 0) return 0;
        if (m <= 0) return 0;

        Tuple<int, int> pair = new Tuple<int, int>(m, n);
        if (!hash.ContainsKey(pair))
        {
            int result = DPCount(coins, m - 1, n, hash) + DPCount(coins, m, n - coins[m - 1], hash);
            hash.Add(pair, result);
        }
        return hash[pair];
    }
}