Coin Change

Problem: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example:

Input: coins = [1,2,5], amount = 12
Output: 3
Explanation: 12 = 5 + 5 + 2

Approach: We are going to use DP here. We can maintain a 1D table where table[i] will tell the minimum number of coins required to make up amount "i". Obviously table[amount] will be our answer. Let's see how to fill this table:

1. FOR i = 0 to amount
• table[i] =  amount + 1
2. table[0] = 0
3. FOR i = 1 to amount
• FOREACH coin in coins // check for each coin
• IF coin <= i
• table[i] = Min (table[i], table[i - coin] + 1) // minimum number of coins for i - coin amount and 1 for this particular coin

That's all!

Implementation in C#:

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

        {

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

            Array.Fill(table, amount + 1);

            table[0] = 0;

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

            {

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

                {

                    if (coins[j] <= i)

                    {

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

                    }

                }

            }

            return table[amount] > amount ? -1 : table[amount];

        }

Complexity: O(m * n) where m is amount and n is length of coins array.