This is like a change-making problem, but you don't want the minimum number of "coins", you want to keep track of the number of ways. Furthermore, it is important to note that order matters. Use dynamic programming as follows. Suppose we want to show how to make 10 from sums of 1, 3, 5 where order doesn't matter (i.e. 1 + 3 + 1 + 5 is the same as 1 + 1 + 3 + 5). Make an array indexed to 10 (11 items). You can make 00 in 1 way. All negative indexes can be made in 0 ways.
00 01 02 03 04 05 06 07 08 09 10
1
You then count the number of ways you can make 1. If you subtract coin value 1 from 1 you get 1. If you subtract any larger coin value from 1, you get a negative index which means zero ways. You sum up the results 1 way (subtracting 1) + 0 ways (subtracting 3) + 0 ways (subtracting 5). So we have
00 01 02 03 04 05 06 07 08 09 10
1 1
Take a value of 2. We can subtract 1 cent coin to get 1 of which there is 1 way; 3 cent coin to get -1 of which there is 0 ways; 5 cent coin to get -3 of which there is 0 ways. Total 1 + 0 + 0 = 1 way to get 2 cents.
00 01 02 03 04 05 06 07 08 09 10
1 1 1
For 3 cents, we can subtract 1 to access all the ways of making change for 2 cents, or subtract 3 cents to access all the ways of making 0 cents, or subtract 5 cents to access all the ways of making -2 cents; sum of ways is 1 + 1 + 0 = 2.
00 01 02 03 04 05 06 07 08 09 10
1 1 1 2
For 4 cents, we can do it in 2 + 1 + 0 = 3 ways. However, note that the 3 ways include 1+1+1+1, 3+1, and 1+3. 1+3 and 3+1 are in different categories since they end in different numbers.
Continuing in this manner, we have
00 01 02 03 04 05 06 07 08 09 10
1 1 1 2 3 5 8 12 19 30 47
Now that we see how to construct the numbers, we can look for faster ways of doing so. Note that we have to deal with negative indices for the first few, which is a bit messy, so we might as well start with the first 5 values as given. What we need to calculate now is a recursive function: f(n) = f(n-1) + f(n-3) + f(n-5) with the condition that f(0),...,f(4) are given by the table above.
There are many ways to calculate that recursive function. This is where it becomes a real test of depth of knowledge. The naive approach would be to use recursion in the programming language. The first problem would be that your numbers will overflow because f has exponential growth. You can mitigate that situation for a time by using long instead of int. But long will quickly overflow too, so you'll have to use BigInteger to get exact results for n bigger than (I'm guessing) 20 or so.
Next, using recursive functions will be slow, because calculating f(n) might involve recalculating smaller f(x) over and over again. To mitigate that problem, use memoization to store f(x) for smaller values. Next, you'll experience stack overflow if you try to calculate from larger n to smaller. If you're calculating for a particular n, you should build up from lower values, instead of down from higher values of n.
Next, you'll experience out of memory. You can get around that by not remembering every value of f(x) as x increases, but only the last 5 values (in my example). Eventually you'll experience out of memory storing BigIntegers, but there's nothing you can do about that unless the question changes.
There are some more accelerations you can use if you're looking to improve the speed of the program. f(n) can be computed in log n operations rather than n operations in the following manner. Note that there is a matrix multiplication way of writing the recursion, where at each stage we need to remember 5 values to calculate the next one:
|1 0 1 0 1| |f(n-1)| | f(n) |
|1 0 0 0 0| |f(n-2)| |f(n-1)|
|0 1 0 0 0| |f(n-3)| = |f(n-2)|
|0 0 1 0 0| |f(n-4)| |f(n-3)|
|0 0 0 1 0| |f(n-5)| |f(n-4)|
So we can calculate f(n) if we can calculate powers of the matrix:
|1 0 1 0 1|^(n-4)
|1 0 0 0 0|
|0 1 0 0 0|
|0 0 1 0 0|
|0 0 0 1 0|
We can accelerate that process by using the binary expansion of n. Suppose n = 6, as it would be if we wanted f(10). Note that 6 = 4 + 2 in binary. Denote the matrix by M. We have M^1. We calculate M^2 = M^1 * M^1 and M^4 = M^2 * M^2, then M^6 = M^2 * M^4.
There may be other accelerations, depending on the particular example, but that should get you started.
