Posted: 23 Oct, 2020
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.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
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.