How to use dynamic programming to solve this?
This is the famous change-making problem.

If you want to solve it with dynamic programming, you have to come up with a suitable recursion. The central question is:


  Assuming you know the optimal coin choices for all $k &lt; n$ (cents), how do you derive the optimal choice of coins for $n$ (cents)?