Dice throw
Problem statement:
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
Explanation:
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
So,
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.
C++ Implementation:
Output
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