Dice Throws

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.

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

Approach 1

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.

Try Problem

Approach 2

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.

Try Problem

Approach 3

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:
1. Loop 1: For i = 1 to D:
2. Loop 2: For j = 1 to S:
3. 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:

Try Problem

Approach 4

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:
1. Loop 1: For i = 1 to D:
2. Loop 2: For j = S to 1:
3. Loop 3: For k = 1 to F:
  if( j-k >= 0 ), DP[j] += DP[j-k]
Return DP[D][S].

Try Problem