By way of enrichment here is a solution in Perl that checks its arguments very carefully and otherwise tries to keep it simple. Here is a sample run for a common choice of denominations:
$ ./change.pl 100 1 2 5 10 20 50
1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 1, 2,
2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3,
4, 4, 3, 4, 4, 5, 5, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4,
4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 3, 4, 4, 5, 5,
4, 5, 5, 6, 6, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 2
And this is the code.
#! /usr/bin/perl -w
#
MAIN: {
my $n = shift;
die "first argument is max value"
if !defined($n);
die "positive integer please: $n"
if $n !~ /^\d+$/ || $n < 1;
my @denoms = ();
while(my $denom = shift){
die "not a positive number: $denom" if $denom !~ /^\d+$/;
die "zero denomination: $denom" if $denom == 0;
die "not in order/duplicate: $denom"
if scalar(@denoms)>0 && $denom <= $denoms[-1];
push @denoms, $denom;
}
die "no denominations" if scalar(@denoms) == 0;
my @OPT =
((undef) x ($n > $denoms[-1] ? $n : $denoms[-1]));
unshift @OPT, 0;
foreach my $denom (@denoms) { $OPT[$denom] = 1 };
for(my $val = 1; $val < scalar(@OPT); $val++){
my $choice = $OPT[$val];
foreach my $try (@denoms) {
my $prev = $val - $try;
last if $prev < 0;
my $count = $OPT[$prev];
if(defined($count)){
if(!defined($choice) || $count+1 < $choice){
$choice = $count + 1;
}
}
}
$OPT[$val] = $choice if defined($choice);
}
shift @OPT;
print join ', ', map {defined($_) ? $_ : 'X'} @OPT;
print "\n";
}