Your solution with 33 seems quite similar to mine, with the 9 missed out and some other minor changes.  I’m trying to check it but don’t want to write code, so perhaps you can help.  How do you reach 9610? 

1, 2, 3, 4, 5, 6, 7, 8, 19, 29, 39, 48, 59, 69, 78, 88, 98, 208, 317, 426, 535, 644, 753, 862, 971, 2051, 3131, 4211, 5291, 6371, 7451, 8531, 9611

To take a very simple example suppose you want to reach all prices up to 24 cents with four coins.  Have a go at finding the fewest denominations for yourself.

Using the original approach I would need five coins: e.g. 1,2,3,6,12  (thinking that 24 = 2x2x2x3, similar to 10,000 = 10x10x10x10, so we need units (1,2), 3’s, 6’s and 12’s).  As before the ‘greedy’ algorithm of taking the highest denomination until we reach zero works.

A better answer uses just three denominations: 1, 5 and 6.  Please check for yourselves.  This time the greedy algorithm does not work.  However there is another algorithm that does.  

24 decimal is 44 in base 5.  1, 5 and 6 decimal are 01, 10 and 11 in base 5.  So we are using every base 5 number, with up to two digits, which only uses 0 and 1.  We get 00 for free, we don’t need to include a zero cent coin.

Let’s see how this works.  Suppose we want to make 14 decimal which is 24 base 5.  24 = 11+11+01+01 base 5, or in decimal 14 = 6+6+1+1.  Hopefully you can see that we can make any number up to 44 base 5 = 24 decimal in this way.

Unfortunately this gets less efficient as we choose higher targets.

If the target was 624 (5^4 -1) then we would need every four digit base 5 number using only 0 and 1 (apart from the number zero).  That is fifteen denominations.  Using the old method would need sixteen denominations.  So we are slightly better but not much.

By the time you get to 10,000 the old method works better. 

In Andy’s solution we can make up to 9 with one single digit coin so we add coins separated by 10 to allow us to reach 99 in two coins.   Next we add coins separated by 100 to get up to 999 with three coins.  Finally adding coins separated by 1000 gets us up to 9999 (and we can also make 10,000 by 9000 + 1000 for example).

This can be optimised by noticing that we can make up to 18 from two single digit coins.  So the double digit coins can start at 19 and continue 29, 39, 49, …, 99.

Now we can make up to 99+9 = 108 with two coins, an improvement on before.  So we can make the gap between the next coins be 109, rather than 100.  Also we can make 108+99=207 with three coins so we can start at 208.  Our next coins are:
  208, 208+109=317, 426, 535, 644, 753, 862, 971

We have saved one coin already, essentially we don’t need the 100 coin because we can get to 200 with three of the smaller coins.

Now we can make up to 971+99+9 = 1079 with three coins, so our next gap will be 1080. We can make up to 1079+971 = 2050 with four coins so we start at 2051.  Our final coins are:
  2051, 3131, 4211, 5291, 6371, 7451, 8531, 9611

Again we have saved a coin by being able to reach 2000 with the lower coins, so we don’t need the 1000 coin.  We can make all values up to 9611+971+99+9 = 10,690 or $106.90.

So our 34 denominations are 
  1, 2, 3, 4, 5, 6, 7, 8, 9,
  19, 29, 39, 49, 59, 69, 79, 89, 99,
  208, 317, 426, 535, 644, 753, 862, 971,
  2051, 3131, 4211, 5291, 6371, 7451, 8531, 9611

To find the right coins for a particular amount the ‘greedy’ algorithm Jeff described should work.  Always take the highest value coin you can until you reach zero.

BTW to have at least 10,000 combinations of four coins you need at least 17 denominations, so this is a lower bound. Interesting that it is half the number you seem to need.

I tried different variations on this, for example add a 109 value coin which saves you a coin later on.  But you always end up needing 34.  Maybe there’s a better way I didn’t try, or maybe there’s a completely different approach.  I can’t prove that 34 is minimal.