A variant of coin change problem
I agree with your solution of the isolated case. Your problem is to reuse your memoisation table. Suppose there are n cases.

What I imagine you could do is:

Allocate a matrix to hold all cases. It has dimensions: T, 1 &lt;= coin value = 50. Call the maximum coin value C. The maximum number of coins is 1000. You could store each count in an unsigned 16 bit int. This max total memory so far of 100 * 50 * 16 = 80KB. We're given 65536, so this isn't too bad. Call this M1.

You now want to devise a plan to reuse your memoisation table as much as possible. As far as I can see, you can reuse a table if and only if the multi-set of coins of the next case is a superset of the previous.

You need to find a way of partitioning the rows into M1 into sequences where each successive vector represents a superset of the previous. That is, the values of coin counts should be non-decreasing over successive vectors.

What you would like to do is minimise the number of partitions. Given two plans with the same number of partitions, you would choose the one which minimises the maximum number of differing coins for a given partition, which would in turn make the solution of the isolated cases cheaper.

I'm not completely sure about the complexity of this, although I imagine that it is NP-Hard, given the number of possible partitions and its similarity to the partition problem. It seems like there might be a cheap randomised greedy algorithm to find a set of initial sequences and work from there.

To run the plan, iterate over the sequences, initialising the memoisation table each time. Run the first case as normal. Run the second case by computing change combinations only for the set of new larger combinations of each coin.