Dice Throws

Posted: 23 Oct, 2020
Difficulty: Hard


Try Problem

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
  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. 
  4. Return answer.
Try Problem