Link Details

In my last post I implemented the greedy algorithm for coin changer in Scala. While greedy algorithms provide optimal solutions for some combinations of coin denominations, it does not offer correct optimal solution for all combinations. In fact, coin changing problem is a well discussed example of a dynamic programming algorithm that exhibits the optimal substructure property, where the optimal solution for the problem can be implemented in terms of optimal solutions of smaller subproblems. Just as a refresher course in basic algorithms and keeping up the spirit of my learning Scala, I thought it might be a good idea to try to implement this in Scala.