Tuesday, February 12, 2013

Understanding Dynamic Programming using C#

Dynamic Programming is quite a cool technique to solve pretty complex problem. One of such problem is Coin Change problem which first seems to be easily solvable using Greedy approach but involves Dynamic Programming in order to get the perfect result in every case. I'm running out of time so posting only code to do that using C#. Will explain next time.


int[] coins;

        public CoinChange()
        {
            coins = new int[5];
            coins[0] = 5;
            coins[1] = 10;
            coins[2] = 20;
            coins[3] = 25;
            coins[4] = 50;
            Console.WriteLine(this.CoinCentral(90));
            Console.ReadLine();
        }

        public int CoinCentral(int input)
        {
            int[] tempCoins = new int[input + 1];
            for (int a = 1; a < tempCoins.Length; a++)
            {
                tempCoins[a] = int.MaxValue;
            }
            tempCoins[0] = 0;

            for (int currentNumber = 1; currentNumber <= input; currentNumber++)
            {
                for (int currentCoin = 0; currentCoin < coins.Length; currentCoin++)
                {
                    if (currentNumber >= coins[currentCoin] && 1 + tempCoins[currentNumber - coins[currentCoin]] < tempCoins[currentNumber])
                    {
                        tempCoins[currentNumber] = tempCoins[currentNumber - coins[currentCoin]] + 1;
                    }
                }
            }
            return tempCoins[input];
        }

No comments:

Post a Comment