I'm having a hard time understanding the logic behind the infamous question, "Find all the ways to reach a certain sum with n cubes of k faces." After searching extensively for explanations, I went out empty-handed.
My confusion stems from the fact that it does not seem to follow the same logic as the "number of ways to make changes to coins" problem that is well explained in a number of videos, especially this one.
My understanding of the problem of money exchange
That's pretty good, I think. When we pass the first row, we are essentially looking at the number of ways to find the target from the first and second coins, not just the second coin (generally, this is the current coin plus all previous coins). , As explained in the linked video, we have to follow some rules:
Simply copy the value from the cell above.
a) Determine the number of ways we can make the target when we EXCLUDE the current coin
b) Determine the number of ways we can make the target when we INCLUDE the current coin
c) Add the two together and store the result in the cell.
For step aWe can determine this by simply copying the value from the cell above: this, after all, is the number of ways we can achieve the same goal without the current coin. So we copy the 0 for 3, that's right; With a 2 coin, there are 0 ways to get the target to 3.
For step bwe have to subtract the current coin from the target, which gives us the rest. Then we have to figure out how many options there are to make that remainder out of the current coin. So for the change of value 3 we have (3-3), which is 0. For a zero goal, there is 1 way to make 0 with a 3 coin, as the table shows (highlighted). So we have 0 + 1 = 1.
I can see how to fill the entire table. The algorithm used is not important here.
My failure to understand the logic of the cube problem
The following algorithm comes from the link above:
long findWays(int f, int d, int s)
// Create a table to store results of subproblems. One extra
// row and column are used for simpilicity (Number of dice
// is directly used as row index and sum is directly used
// as column index). The entries in 0th row and 0th column
// are never used.
long mem(d + 1)(s + 1);
// Table entries for no dices
// If you do not have any data, then the value must be 0, so the result is 1
mem(0)(0) = 1;
// Iterate over dices
for (int i = 1; i <= d; i++)
// Iterate over sum
for (int j = i; j <= s; j++)
// The result is obtained in two ways, pin the current dice and spending 1 of the value,
// so we have mem(i-1)(j-1) remaining combinations, to find the remaining combinations we
// would have to pin the values ??above 1 then we use mem(i)(j-1) to sum all combinations
// that pin the remaining j-1's. But there is a way, when "j-f-1> = 0" we would be adding
// extra combinations, so we remove the combinations that only pin the extrapolated dice face and
// subtract the extrapolated combinations.
mem(i)(j) = mem(i)(j - 1) + mem(i - 1)(j - 1); // CONFUSION POINT A
if (j - f - 1 >= 0)
mem(i)(j) -= mem(i - 1)(j - f - 1); // CONFUSION POINT B
I've read this code over and over again, maybe too often, but I just do not understand it.
Number of cubes (
d) = 3, number of faces on each die (
f) = 3, target value (
s) = 3. I've added some debugging issues and generated the following to show how the cells in my spreadsheet are calculated:
(1,1) = (1,0) + (0,0)
(1,2) = (1,1) + (0,1)
(1,3) = (1,2) + (0,2)
!! (2,1) is never calculated, CONFUSION POINT C !!
(2,2) = (2,1) + (1,1)
(2,3) = (2,2) + (1,2)
Having parsed the algorithm into plaintext shows that
the number of ways of making 3 with 2 dice (2,3) is
the number of ways of making 2 with 2 dice (2,2) +
the number of ways of making 2 with 1 die (1,2)
At this point, it does not seem to follow the logic of the coin change problem; That is, the pseudo code block I posted above. I even tried to specify the numeric values to apply this logic. i.e. the 1 is (1) and the 2 is (2,1) to follow a similar idea as "adding extra coins", but it just does not work. This is worrisome for me because, while I understand the (beautiful) concept behind dynamic programming, it does not seem to be able to apply the same logic to all similar problems of this kind.
Can someone please explain my three confusion points to me:
a) How it works and the logic behind it.
b) What on earth is this line doing?
c) Why is cell (2,1) never calculated? I'm pretty sure now that this is simply because we can never make 1 of 2 dice, but I'd like to confirm that if I missed something.