# Dice Throws

#### You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

##### Note :

```
As the answer can be large, return your answer modulo 10^9 + 7.
```

##### Follow Up :

```
Can you solve this using not more than O(S) extra space?
```

##### Input format :

```
The first line of input contains an integer T denoting the number of test cases.
The first and the only line of every test case contains 3 integers D, F and S representing the number of dices, the number of faces on each die and the target sum respectively.
```

##### Output format :

```
For each test case, print the number of ways to get the sum S in a separate line.
```

##### Note :

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 5
1 <= D, F <= 50
1 <= S <= 10^3
Time limit: 1 sec
```

- The idea is to use recursion to reduce the big problem into several small subproblems.
- We will call a helper function that returns us the number of combinations that sum upto S and store it in a variable say answer.
- The algorithm for the helper function will be as follows:

Int helper(D, F, S):

A. If D as well as S becomes 0, return 1.

B. If D becomes 0 or S becomes negative, return 0.

C. Initialise a count variable say finalCount with 0.

D. For i = 1 to F:

Call helper function for D-1 and S-i, add it to the finalCount.

finalCount += helper(D-1, F, S-i)

E. Return finalCount.

- Return answer.

**Let’s understand by an example **

Suppose we have 3 dice each with 6 faces and we have to find the number of ways to achieve the sum 8.

The below figure shows some of the recursive calls are made for the given problem.

**Note:** Subproblem {a,b,c} means a problem with ‘**a’** dice each with ‘**b’** faces and ‘**c’ **is the desired sum.

As we can see, some subproblems are called multiple times.

For example, the subproblem {1,6,5} is called 2 times, {1,6,3} is called 4 times and {1,6,1} is called 6 times.

That’s why we are storing the solved subproblems in a lookup table so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the lookup table.

**Approach: **

- The idea is to use memoization.
- Create a 2D lookup table to store the solutions to the subproblems where lookUp[i][j] denotes the possible number of ways to get sum j with i number of dice/die.
- Initialize the table by -1.
- Now, we call a helper function that returns us the number of combinations using D dice with F faces that sum up to S and store it in a variable say answer.
- The algorithm for the helper function will be as follows:

Int helper(D, F, S):

A. If D, as well as S, becomes 0, return 1.

B. If D becomes 0 or S becomes negative, return 0.

C. If lookUp[D][S] is not equal to -1, return lookUp[D][S].

D. Initialise a count variable say finalCount with 0.

E. For i = 1 to F:

Call helper function for D-1 and S-i, add it to the finalCount.

finalCount += helper(D-1, F, S-i)

F. Update lookUp[D][S] with finalCount.

G. Return lookUp[D][S]

- Return answer.

- The idea is to create a 2-D DP with row size D+1 and column size S+1.
- Initially all the elements of the DP table will be 0.
- Now, the value DP[i][j] means the possible number of combinations with i dice and j sum. Thus, initialise DP[0][0] as 1.
- The detailed algorithm to fill the DP table will be as follows:
- Loop 1: For i = 1 to D:
- Loop 2: For j = 1 to S:
- Loop 3: For k = 1 to F:

if( j-k >= 0 ), DP[i][j] += DP[i-1][j-k]

- Return DP[D][S].

**Let us understand the above algorithm in detail with an example: **

For the test case where D = 3, F = 6 and S = 4

- We will create a DP table with 4 (D + 1) rows and 5 columns (S +1) with all elements as 0.

Now, for 0 number of Die, we have 1 way for getting 0 sum. Thus, DP[0][0] should be 1.

- In the next step when we are at DP[1][1], this means that we have to fill the number of ways to get a sum of 1(S) with 1(D) die. This can be found by letting a number 1 on 1 die and fetching the possible number of combinations for 0(D-1) die having 0(S-1) sum which is at DP[0][0]. Thus, DP[1][1] becomes 1.
- Now, let's take number 2 on 1 die and fetch the possible number of combinations for 0(D-1) die having -1 (S-2) sum. Note that negative sum is not possible to achieve and thus we stop traversing further.
- Similarly, for DP[1][2] will be DP[0][1] + DP[0][0] and so on DP[1][4] will be DP[0][3] + DP[0][2] + DP[0][1] + DP[0][0].

The table will be:

- In the next iteration, we are at DP[2][1], this means that we have to fill the number of ways to get a sum of 1(S) with 2(D) dice. This can be found by letting a number 1 on 1 die and fetching the possible number of combinations for 1(D-1) die having 0(S-1) sum i.e DP[1][0]. Thus, DP[2][1] becomes 0.
- Now, let's take number 2 on 1 die and fetch the possible number of combinations for 1(D-1) die having -1 (S-2) sum. Note that negative sum is not possible to achieve and thus we stop traversing further.

We will notice:

DP[2][2] = DP[1][1] + DP[1][0]

DP[2][3] = DP[1][2] + DP[1][1] + DP[1][0]

DP[2][4] = DP[1][3] + DP[1][2] + DP[1][1] + DP[1][0]

The table becomes:

Similarly, the final table will be:

- The idea is to create a 1-D DP of size S+1.
- Initially, all the elements of the DP table will be 0.
- We can make only S = 0 with 0 dice, so dp[0] = 1,
- The detailed algorithm to fill the DP table will be as follows:
- Loop 1: For i = 1 to D:
- Loop 2: For j = S to 1:
- Loop 3: For k = 1 to F:

if( j-k >= 0 ), DP[j] += DP[j-k]

- Return DP[D][S].