Dynamic Programming

e.g. how to make change for 49 cents: 25 10 10 1 1 1 1

but if coins available are 1 3 6 12 24 30 60
and give change for 48 pence: 30 12 6
but best way is 24 24

Number of different ways to give change for e.g. 49 cents
1) 25 10 10 1 1 1 1
2) 25 10 5 5 1 1 1 1
3) 25 10 5 1 1 1 1 1 1 1 1 1
4) 25 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1
and so on for quite a while

We want to know the number of different combinations of coins that still add up to 49.

here the first binary decision is do we use a quarter or not?

Yes, we do use a quarter.
   left with the problem of giving 24 cents also being allowed to use 25 10 5 1
      and recursively continue with that problem

No, we don't use a quarter.
   left with the problem of giving 49 cents being allowed to us only 10 5 1
      and recursively continue with that problem

Finally add together two totals that we get from the two recursions.

Two parameters to the recursion
   1: the amount of money remaining to give change for
   2: the entries in the array of coin values that we're still allowed to use.

int values[] = { 1, 5, 10, 25 };

int ways(int amount, int last_usable /* starts off as 3 */)
{ if (amount == 0)
    return 1;     // the result is the empty set of coins, that's still a valid solution
  if (last_usable < 0)
    return 0;
  if (amount < values[last_usable]) // can't use that coin at all, it is too big
    return ways(amount, last_usable - 1);
  int n1 = ways(amount - values[last_usable], last_usable);
  int n2 = ways(amount, last_usable - 1);
  return n1 + n2; }