# Dice Throws

Posted: 23 Oct, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### 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.
``````
``````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
`````` Approach 1
1. The idea is to use recursion to reduce the big problem into several small subproblems.
2. 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.
3. 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.