how to pay n cents

How many different ways can you pay n cents using cents, nickels, dimes, quarters, and half-dollars? Let the answer be A_n. This is the first problem in Problems and Theorems in Analysis I. Let f_coin[n] be a discrete signal that equals 1 when n is a non-negative multiple of the coin, and 0 everywhere else:

Ex. f_nickel[-1] = 0, f_nickel[1] = 0, f_nickel[5] = 1, f_nickel[6] = 0, ...

This is just like a forward echo, except the "future" filter taps are not attenuated

 (f_cent*f_nickel*f_dime*f_quarter*f_half-dollar)[n] = A_n, where * is the convolution operator. This can be computed via dynamic programming. Start with f_cent[n] by setting dp[n] = 1 for all 0 ≤ n ≤ 100, then convolve with the next coin signal. This amounts to applying this update rule from n=1 to n=100: dp[n] ← dp[n] + dp[n - coin_value].

If order of payment matters, then the solution is a simple linear recurrence. A_n = A_{n - 1} + A_{n - 5} + ... + A_{n - 50}.

Dynamic programming solutions to equivalent cses problems:

https://cses.fi/paste/ea7be550e17f258fb775bb/

https://cses.fi/paste/adf1b5540ddf073e6456ca/