Multisets of Exactly k Coins
Coins of m distinct denominations are available in unlimited supply. Count the
MULTISETS of exactly k coins summing to exactly amount. Order does not matter.
Print the count modulo 1000000007.
coins 1 2 3, k = 3, amount = 6 -> 2 {1,2,3} and {2,2,2}
coins 1 2 3, k = 4, amount = 8 -> 3 {1,1,3,3} {1,2,2,3} {2,2,2,2}
coins 1, k = 3, amount = 4 -> 0 three 1s cannot make 4
Problem 482 counts multisets with no size restriction. Pinning the size adds an axis, and the interest is in what each of the three loops now has to do.
## The table
dp[j][v] = multisets of exactly j coins summing to exactly v
dp[0][0] = 1
for each denomination c: outer, for MULTISETS
for j in 1..k: ascending, for UNLIMITED supply
for v in c..amount: ascending
dp[j][v] += dp[j-1][v-c]
## Three loops, three separate reasons
The DENOMINATION loop is outermost, and that is what makes the count a count of multisets rather than sequences, exactly as in problem 482: each multiset is counted once, when its highest-indexed denomination is introduced.
The COUNT loop ascends. Within one denomination, dp[j][v] reads dp[j-1][v-c], which
must already include uses of the SAME denomination if that coin is to be used more than
once. Ascending j provides that. Descending j would give at-most-one-of-each, which
is a different problem.
The VALUE loop ascends too, but here it does not matter: dp[j][v] only ever reads row
j-1, never row j, so nothing in this row is read after being written. Being able to
say which loop directions are load-bearing and which are free is the useful part.
## Why the count axis replaces the usual unbounded trick
In problem 482 unlimited supply came from reading dp[v - c] in the SAME row, already
updated. Here the read is always from j-1, so that mechanism is gone, and repetition of
a coin is expressed by descending one step in j instead.
Two different encodings of the same freedom, and the size axis is what makes the second one available.
## Boundaries
coins 1, k = 3, amount = 3 answers 1 and k = 3, amount = 4 answers 0. With a single
denomination the size and the total determine each other, so almost every pair is
impossible, which is the cleanest check that both axes are being respected.
coins 5, k = 2, amount = 10 answers 1.
amount and k are independent, so an answer of 0 is common and correct. It is never
-1.
## Cost
Time O(m * k * amount). Space O(k * amount).