The Coin Change Problem (Solution for https://www.hackerrank.com/challenges/coin-change)

coins_change_problem.cs

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace coinchange
{

    struct DpEntry
    {
        public DpEntry(int n, int i)
        {
            this.n = n;
            this.i = i;
        }
        public int n;
        public int i;
    }
    class Program
    {
        private static Dictionary<DpEntry, Int64> dp;
        static void Main(string[] args)
        {
            var x = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var coins = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            dp = new Dictionary<DpEntry,Int64>();
            Console.WriteLine(changeDp(coins, x[0], 0));
            
            Console.ReadKey();
        }

        //Non dp solution
        static int change(int[] coins, int n, int i)
        {
            if(n == 0)
            {
                return 1;
            }

            return (n - coins[i] < 0 ? 0 : change(coins, n - coins[i], i)) + (i + 1 < coins.Length ? change(coins, n, i + 1) : 0);
        }

        //Dp solution using the memoization to store and reuse redundant calls made
        static Int64 changeDp(int[] coins, int n, int i)
        {
            if(n == 0)
            {
                return 1;
            }

            if(!dp.ContainsKey(new DpEntry(n,i)))
            {
                dp[new DpEntry(n,i)] = (n - coins[i] < 0 ? 0 : changeDp(coins, n - coins[i], i)) + (i + 1 < coins.Length ? changeDp(coins, n, i + 1) : 0);
            }

            return dp[new DpEntry(n,i)];
        }
    }
}