Minimum number of coins to make change

We should give a certain amount back, and we want minimize the number of coins involved in the operation, accordingly to the available denominations. So, for instance, we have only copper Euro cents (1, 2, 5) and the change should be 4. In this case the expect result is 2, a couple of 2c coins.

We could think to use a greedy procedure, and sometimes it works beautifully, as in example I showed above. However it does not work for all possible denominations. As a counterexample think what happens if we have to generate 40 from (1, 5, 10, 20, 25). The greedy solution is 3, 25c + 10c + 5c, while the optimal solution is 2, 20c + 20c.

Actually, this problem is commonly used to introduce dynamic programming, where the idea is solving all the subproblems originating from the required one, starting from the simplest ones, and using those partial solutions to build up the more complex ones.

Here is a possible Java solution:

public static int minNumCoins(int amount, List<Integer> coins) {
 assert (amount >= 0); // 1
 assert (isConsistent(coins)); // 2

 List<Integer> results = new ArrayList<>(amount + 1); // 3
 results.add(0); // 4
 for(int i = 1; i <= amount; ++i) { // 5
  results.add(Integer.MAX_VALUE); // 6
  for(int coin : coins) { // 7
   if(coin > i)
    break;

   int tentative = results.get(i - coin) + 1; // 8
   if(tentative < results.get(i)) {
    results.set(i, tentative);
   }
  }
 }

 return results.get(results.size() - 1); // 9
}

1. I assert that the required amount should be not negative.
2. I have delegate to an helper method the consistency check on the coin list. I assume the requisite are that it should not be empty, it has to start from 1, and to be sorted.
3. I'm going to store in this array-list the results for the subproblems and the problem itself. When a step would required a previously calculated subsolution, it would get the result from this list. This technique is known as memoization.
4. Base case. An amount of zero requires no coin.
5. Let's calculate all the subproblems before generating the result for the actual one.
6. Initialize the current solution to the worst possible value.
7. Check it against all available coins, assuming the list being sorted, see (2), we can stop looping as soon as we see a coin greater than the index of current element in the list.
8. A tentative solution is the number of tentatives for the previous intermediate step plus one. If this try is better than the current tentative solution, let's use it as candidate.
9. Now we just have to return the last item in the result array-list.

Full Java code is on github. There you will find, beside the code you have already seen above, in the same class CoinChanger also a greedy implementation, that is going to fail in some cases. Also a JUnit suite of test cases is there.