# 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 oneWe can think of the recursive function as

f(n,X)wherenis number of dice andXis desired sum.A single dice has

mchoices, which means the face can have values ranging 1 tomSo,

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=6So, 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 mBut this recursion will generate many overlapping sub problems, hence, we need to convert it to dynamic programing.

C++ Implementation:OutputIn the second output there is no way to acquire the sum which can be verified as

need an explanation for this answer? contact us directly to get an explanation for this answerm*n<X. It's better practise to keep such base case to optimize your code :)