Solution to dynamic programming problem of creating optimal change with least number of coins. Solution includes greedy and dynamic problems as well as comparisons between them.

DynamicProgrammingChangeProblem.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

// The change problem :D
namespace DynamicProgramming
{
    class Program
    {
        public readonly static Dictionary<String, int> coins = new Dictionary<String, int>()
        {
            { "One", 1 },
            { "Three", 3 },
            { "Four", 4 },
        };

        static void Main(string[] args)
        {
            optimalChange[0] = new Dictionary<string, int>() {
                { "One", 0},
                { "Three", 0},
                { "Four", 0 },
            };
            for (int i = 1; i < 100; i++)
            {
                var changeDefault = CalculateChange(i);
                var changeDynamic = CalculateChangeDynamic(i);
                Console.WriteLine("DEFAULT " + i + ": " + Stringify(changeDefault) + " | " + CalculateCoinAmount(changeDefault));
                Console.WriteLine("DYNAMIC " + i + ": " + Stringify(changeDynamic) + " | " + CalculateCoinAmount(changeDynamic));
                Console.WriteLine();
            }
            Console.ReadLine();
        }

        private static Dictionary<string, int>[] optimalChange = new Dictionary<string, int>[100];

        private static Dictionary<String,int> CalculateChangeDynamic(int change)
        {
            var resultingChangeAmounts = new Dictionary<string, int>();
            int currentBestExchange = Int32.MaxValue;
            foreach (var coin in coins)
            {
                int targetIndex = change - coin.Value;
                if (targetIndex < 0)
                {
                    continue;
                }
                int coinAmount = CalculateCoinAmount(optimalChange[targetIndex]);
                if (coinAmount > currentBestExchange)
                {
                    continue;
                }
                currentBestExchange = coinAmount;
                var tempChange = new Dictionary<string, int>(optimalChange[targetIndex]);
                int value = tempChange[coin.Key] + 1;
                tempChange.Remove(coin.Key);
                tempChange.Add(coin.Key, value);

                resultingChangeAmounts = tempChange;
            }
            optimalChange[change] = resultingChangeAmounts;
            return resultingChangeAmounts;
        }

        private static int CalculateCoinAmount(Dictionary<string, int> resultingChangeAmounts)
        {
            int coinCount = 0;
            foreach (var coin in resultingChangeAmounts)
            {
                coinCount += coin.Value;
            }
            return coinCount;
        }

        private static Dictionary<String, int> CalculateChange(int change)
        {
            var resultingChangeAmounts = new Dictionary<string, int>();
            foreach (var coin in coins.OrderByDescending((kv) => kv.Value))
            {
                int coinAmount = 0;
                while (change >= coin.Value)
                {
                    coinAmount++;
                    change -= coin.Value;
                }
                resultingChangeAmounts.Add(coin.Key, coinAmount);
            }
            return resultingChangeAmounts;
        }

        private static string Stringify(Dictionary<string, int> resultingChangeAmounts)
        {
            StringBuilder builder = new StringBuilder();
            foreach (var coinAmount in resultingChangeAmounts)
            {
                builder.Append(coinAmount.Key);
                builder.Append(":");
                builder.Append(coinAmount.Value);
                builder.Append(" ");
            }
            return builder.ToString();
        }
    }
}