Dice Throws

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.

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: 

1. The idea is to use memoization.
2. 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.
3. Initialize the table by -1.
4. 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.
5. 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] 
    
6. 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:
  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:

• 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].