using System;

public class Program

{

    static int counter = 0;

    static int[] foundCoins = new int[10];

    public static void Main()

    {   

        //Console.WriteLine("...Number of coins= " + CoinChange(3,new int[]{1,2}));

        //Console.WriteLine("...Number of coins= " + CoinChange2(12,new int[]{1,5,6,9}));   

        //Console.WriteLine("...Number of coins= " + CoinChange(11,new int[]{1,2,5}));

        Console.WriteLine("=> amount: 11 | coins: 1, 2, 5");

        Console.WriteLine("...Number of coins= " + CoinChange11(11,new int[]{1,2,5}));

        counter=0;

        Console.WriteLine("\n=> amount: 3 | coins: 5, 9");

        Console.WriteLine("...Number of coins= " + CoinChange11(3,new int[]{5,9}));

        counter=0;

        Console.WriteLine("\n=> amount: 12 | coins: 1, 5, 6, 9");

        Console.WriteLine("...Number of coins= " + CoinChange11(12,new int[]{1,5,6,9}));

        //Console.WriteLine("...Number of coins= " + CoinChange2(11,new int[]{1,2,5}));

    }

    public static int CoinChange(int x, int[] coins)

        {

            //Console.WriteLine("input amount: " +x);

            if ( x == 0 )

            {

                //Console.WriteLine("returning zero");

                return 0;

            }

            int min = x;

            foreach (int coin in coins)

            {

                Console.WriteLine("x: " +x+ " | coin:" + coin);

                if(x-coin >= 0)

                {

                    var diff = x-coin;

                    //Console.WriteLine("x: " +x+ " | coin:" + coin + " | x-coin= " + diff);

                    int val = CoinChange(x- coin, coins);

                    if (min > val + 1)

                    {

                        var newVal = val+1;

                        Console.WriteLine(">>> min: " +min+ " | val+1:" + newVal);

                        min = val + 1;

                    }

                }

            }

            return min;

        }

    public static int CoinChange11(int x, int[] coins)

    {

        //Console.WriteLine("input amount: " +x);

        if (x == 0) return counter;

        for(int i=coins.Length-1; i>=0; i--)

        {

            //var y = x-coins[i];           

            //Console.WriteLine("x: " +x+ " | coin:" + coins[i] + " | x-coin= " + y);

            Console.WriteLine("x: " +x+ " | coin:" + coins[i]);

            if (coins[i] <= x)

            {

                counter++;

                //Console.WriteLine(">>>>>>> recurse: counter="+ counter);

                return CoinChange11(x-coins[i], coins);

            }

        }

        Console.WriteLine("returning -1");

        return -1;

    }

    public static int CoinChange2(int amount, int[] coins)

        {

            int[,] arr = new int[coins.Length, amount+1];

            int min=0;

​

            for (int i=0; i<coins.Length; i++)

            {

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

                {

                    if(i==0 || j==0)

                    {

                        arr[i,j] = j;

                    }

                    else

                    {

                        if(coins[i] > j)

                        {

                            arr[i,j] = arr[i-1,j]; // copy value from cell above

                        }

                        else

                        {

                            arr[i,j] = Math.Min(arr[i-1,j], 1 + arr[i,(j-coins[i])]);

                        }

                    }

                    min = arr[i,j];

                }

            }

            return min;

        }

}