using System;

​

public class Solution {

    public static int CoinChange(int[] coins, int amount) {

        //DP init

        int[] dp = new int[amount + 1];

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

        {

            dp[i] = amount + 1;

        }

        dp[0] = 0;

        for(int sum = 1; sum <= amount; sum++)

        {               

            foreach(int coin in coins)

            {

                if(sum-coin >= 0)

                    dp[sum] = Math.Min(dp[sum], dp[sum-coin] + 1);

            }

            /*

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

            {

                if(sum - coins[i] >= 0)

                {

                    dp[sum] = Math.Min(dp[sum], dp[sum- coins[i]] + 1);

                }

            }

            */

        }

        return dp[amount] == (amount + 1) ? -1 : dp[amount];

    }

    public static void Main()

    {

        int result = CoinChange(new int[]{1, 2, 5}, 11);

        Console.WriteLine(result);

    }

}