먼저 문제를 하위 문제들로 분할해서 Recursive를 이용해 푼 예는 아래의 Count() 함수이고, 보다 최적화하기 위해서 중간 결과를 저장(Memoization)하여 Lookup하는 방식을 사용한 것이 DPCount()이다.

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];
    }
}