project euler problem 031

Coin sums

I like this problem. Although it is simple,  I still learned a lot from this problem. 

There are several ways to solve this problem: Generating function; dynamic programming,  recursion.  Recursion is the most natural way to solve this problem. 

Update (06/17/2017):

The problem may look simple,  actually the dynamic programming way is the only simple choice for large N. The recursive way only works for small N. For large N, it is extremely slow.  The code in the overview of this problem worth the time to read, especially the one by wizeman.