using System;

​

​

namespace Algorthimica.DP

{

    public class MaxCoins

    {

        int[,] inputGrid = {

                            { 4, 3, 6, 3 },

                            { 30, 8, 4, 7 },

                            { 3, 2, 9, 5 },

                            { 6, 5, 3, 1 },

                            { 8, 6, 7, 4 }

        };

        int[,] outputGrid = new int[5, 4];

        int globalCount = 0;

​

        internal int Execute(int row, int col, int currentMax)

        {

            if (row < 0 || col < 0)

            {

                return 0;

            }

            globalCount++;

            currentMax = currentMax + Math.Max(Execute(row - 1, col, currentMax), Execute(row, col - 1, currentMax)) + inputGrid[row, col];

            outputGrid[row, col] = currentMax;

​

            return currentMax;

        }

​

        internal void Execute()

        {

            int sum = this.Execute(4, 3, 0);

            Console.WriteLine("Max Coins : " + sum);

​

            for (int i = 0; i < 5; i++)

            {

                for (int j = 0; j < 4; j++)

                {

                    Console.Write(outputGrid[i,j]+" ");

                }

                Console.WriteLine("");

            }

​

            Console.WriteLine("No of calls for caluculating the optimum path " +globalCount);

        }

    }

    public class MaxCoinsTest

    {

        public static void Main(string[] args)

        {

            MaxCoins num = new MaxCoins();

            num.Execute();

            Console.ReadLine();

​

        }

    }

}

​