# Dice Throw

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.

The **Naive approach** is to find all the possible combinations of values from n dice and keep on counting the results that sum to X.

This problem can be efficiently solved using **Dynamic Programming (DP)**.

```
Let the function to find X from n dice is: Sum(m, n, X)
The function can be represented as:
Sum(m, n, X) = Finding Sum (X - 1) from (n - 1) dice plus 1 from nth dice
               + Finding Sum (X - 2) from (n - 1) dice plus 2 from nth dice
               + Finding Sum (X - 3) from (n - 1) dice plus 3 from nth dice
                  ...................................................
                  ...................................................
                  ...................................................
              + Finding Sum (X - m) from (n - 1) dice plus m from nth dice

So we can recursively write Sum(m, n, x) as following
Sum(m, n, X) = Sum(m, n - 1, X - 1) + 
               Sum(m, n - 1, X - 2) +
               .................... + 
               Sum(m, n - 1, X - m)
```

**Why DP approach?**\
The above problem exhibits overlapping subproblems. See the below diagram. 

Let there be 3 dice, each with 6 faces and we need to find the number of ways to get sum 8:

![](https://tutorialspoint.dev/image/diceThrow2-1024x359.png)

\ <br>

![](https://99772386-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Ml1CeryuEyvAp_NEaaR%2Fuploads%2FniPEJS5IQ61f9JtMfsTA%2Fimage.png?alt=media\&token=ebfd809f-7ca9-4fb6-8a66-6fa376d2475c)

Please take a closer look at the above recursion.&#x20;

The sub-problems in RED are solved first time and sub-problems in BLUE are solved again (exhibit overlapping sub-problems). Hence, storing the results of the solved sub-problems saves time.