Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
Input: n=3 m=3 X=6 Output: Total number of ways are: 7
Total number of dices: 3 say x1,x2,x3 Number of faces on each dice: 3 (1 to 3) Total sum to be achieved: 6 We will write as xi(j)which means face value of dice xi is j So sum 6 can be achieved in following ways: 6=x1(1)+x2(2)+x3(3) 6=x1(1)+x2(3)+x3(2) 6=x1(2)+x2(2)+x3(2) 6=x1(2)+x2(3)+x3(1) 6=x1(2)+x2(1)+x3(3) 6=x1(3)+x2(2)+x3(3) 6=x1(3)+x2(3)+x3(1) This are total 7 ways to achieve the sum.
If it was only 1 dice, then if X<=m, the answer would be 1 else 0. Since there is only one way to achieve the sum if possible as there is only one dice.
Now when n, number of dice>1, then the problem becomes a recursive one
We can think of the recursive function as f(n,X) where n is number of dice and X is desired sum.
A single dice has m choices, which means the face can have values ranging 1 to m
Recursively we can write,
That means summation of all choices for this particular dice to have face value 1 to minimum(X, m)
For our example case, n=3, m=3, X=6
So, we need to find f(3,6)
f(2,5), f(2,4), f(2,3) all are sub problems themselves which are needed to be solved further. This would generate a recursion tree.
Of course, we have base cases for single dice which is f(1,i)=1 for i=1 to m
But this recursion will generate many overlapping sub problems, hence, we need to convert it to dynamic programing.
In the second output there is no way to acquire the sum which can be verified as m*n<X. It's better practise to keep such base case to optimize your code :)need an explanation for this answer? contact us directly to get an explanation for this answer