Sorry I had a logic flaw at first.

for all n < 0: a(n) = 0

a(0) = 1

for all n > 0: a(n) = a(n-1) + a(n-2) + 2*a(n-5) + 2*a(n-10) + a(n-20) + a(n-100)

Now my answer agrees with the problem statement. Safe to ignore what I wrote below.

~~~~~~ Begin original response ~~~~~~~

This is common for the problem solving necessary for various computer science problems.

Say a(n) is the number of ways to pay. If you pay with a 1 cent coin, you're left with n-1 coins. If you pay with a 2 cent coin, you're left with n-2 coins.

Define: for all n 0, a(n) = 0.

Define b(n) such that b(1) = 1; b(2..4) = 2 meaning b(2)=2, b(3)=2, b(4)=2; b(5..9) = 4; b(10..19) = 6; b(20..99) = 7; b(100..) = 8.

Then for all n > 0: a(n) = b(n) + a(n-1) + a(n-2) + 2*a(n-5) + 2*a(n-10) + a(n-20) + a(n-100).

Programmatically, we could implement with if-then statements;

if (n < 1) return 0;

s = 1 + a(n-1);

if (n > 1) s += 1 + a(n-2);

if (n > 4) s+= 2 + 2*a(n-5);

etc.

Edit: Hmm I'm getting a(17) = 14227, maybe I mistyped something. Edit 2: After fixing a bug, I now consistently get a(17)=21727 with the two different implementations given above. Can someone help decide whether this is right or the problem statement is right?

~~~~~~ End original response ~~~~~~~