There are d dice each having f faces. We need to find the number of ways in which we can get sum s from the faces when the dice are rolled.

Let us first understand the problem with an example-

• If there are 2 dice with 2 faces, then to get the sum as 3, there can be 2 ways-

1. 1st die will have the value 1 and 2nd will have 2.
2. 1st die will be faced with 2 and 2nd with 1.

Hence, for f=2, d=2, s=3, the answer will be 2.

Approach -

1) BRUTE FORCE -
The naive approach is to find all the possible combinations using for loops for each dice and then calculating the sum of all the faces, to check if we get the value as s. We will use another variable to keep count of how many times we get sum as s, and the value of this count variable will be our answer.

However, this approach is very time consuming and lengthy and its time complexity will depend on the number of dice.

Time complexity: O(d^2 * f) as:

• There are d * f combinations
• For each combination, we will need O(d) time to get the sum

2) DP Approach -

We can solve this problem efficiently with Dynamic Programming. For that, we need to first understand the basic structure -

Let the function for number of ways to find sum s from d dice with f faces be Sum(f,d,s)

Sum(f,d,s) = 
[getting sum (s-1) from (d-1) dice when dth die has value 1]  
+  [getting sum(s-2) from (d-1) dice when dth die has value 2]  
+  [getting sum(s-3) from (d-1) dice when dth die has value 3] 
+ .................................................................
+  [getting sum(s-f) from (d-1) dice when dth die has value f]

The dth die can have the maximum value f as there are only f faces in the dice.

Let us understand this concept with an example :

• f = 5, d = 3, s = 8

Hence, we have 3 dice with 5 faces, and we need to find the number of ways to get the sum as 8.

Sum(5,3,8) = 3rd die getting 1 + 3rd die getting 2 + 3rd die getting 3 + ...... + 3rd die getting 5

Sum(5,3,8) = Sum(5,2,7) + Sum(5,2,6) + Sum(5,2,5) + Sum(5,2,4) + Sum(5,2,3)
//The 3rd die can have maximum value of 5, as there are 5 faces. Hence we'll stop at Sum(5,2,3)

Also,
Sum(5,3,7) = Sum(5,2,6) + Sum(5,2,5) + Sum(5,2,4) + Sum(5,2,3) + Sum(5,2,2)
//With 2 dice, the minimum sum must be 2.

Hence, we get-
Sum(5,3,8) = Sum(5,3,7) + Sum(5,2,7)

Therefore, in general terms -
Sum(f,d,s) = Sum(f,d,s-1) + Sum(f,d-1,s-1)

We can further find Sum(5,2,7) as-
Sum(5,2,7) = Sum(5,1,6) + Sum(5,1,5) + Sum(5,1,4) + Sum(5,1,3) + Sum(5,1,2)

However, Sum(5,1,6) = 0, as we can't have a sum  of 6 with 1 die having 5 faces.

Therefore, 
Sum(5,2,7) = Sum(5,1,5) + Sum(5,1,4) + Sum(5,1,3) + Sum(5,1,2)

This process continues throughout the whole equation.

• Sum(f,1,s) will always be 1 when s<=f, as with one die, there is only one way to get sum s.
• Sum(f,1,s) will be 0 when s>f, as there are not sufficient number of faces or dice, to get sum s. So, there are 0 ways.

Hence, is our example -
Sum(5,2,7) = 1 + 1 + 1 + 1 = 4

In this way, we can call each function and eventually find the Sum(5,3,8). We will store all the values in a 2d table[i][j] where i will go upto d and j will upto s. We will use this dp table[i][j] to find other values and so on..

Hence, we need a base value-
Sum(f,0,0) = 1
i.e table[0][0] = 1

• Time Complexity: O(n * x)
  where n is number of dice and x is given sum.

Code

The following is the code of the abouve problem in C++

#include<bits/stdc++.h> 
using namespace std; 
  
long numOfWays(int f, int d, int s) 
{ 
    //Creata a 2d table with one extra row and column for simplicity. 
    long table[d + 1][s + 1]; 

    //Initialise the table with 0.
    memset(table,0,sizeof table); 

    
    // Base value
    table[0][0] = 1; 

    // Iterate over dice
    for (int i = 1; i <= d; i++) 
    { 
        // Iterate over sum 
        for (int j = i; j <= s; j++) 
        { 
            //general equation to obtain Sum(f,s,d)
            table[i][j] = table[i][j - 1] + table[i - 1][j - 1]; 

            //Some extra values are added when j>f 
            // i.e when sum to be found is greater than the number of faces. 
            // Such values need to removed.
            if (j > f) 
                table[i][j] -= table[i - 1][j - f - 1]; 

        } 
    } 
    return table[d][s]; 
} 
  

int main(){
    cout << numOfWays(4, 2, 1) << endl; 
    cout << numOfWays(2, 2, 3) << endl; 
    cout << numOfWays(6, 3, 8) << endl;
    cout << numOfWays(5, 3, 8) << endl;  
    cout << numOfWays(4, 2, 5) << endl;  
    cout << numOfWays(4, 3, 5) << endl;  

}

Output -

0
2
21
18
4
6

Workflow -

Let us walkthrough the code with our previous example - Sum(5,3,8)

We are using nested for loops to traverse through the table, where i denotes number of dice, and j denotes the sum to find.

We are computing the sum and storing it in the table with our general formula-
Sum(f,d,s) = Sum(f,d,s-1) + Sum(f,d-1,s-1)

Hence,
table[i][j] = table[i][j-1] + table[i-1][j-1]

We are starting from i=1 and j=1, and finding all the values of table[i][j] till we reach i=d and j=s.

However, for some cases, extra values are added according to this general equation.

• For example, from our code, we can see that -
  Sum(5,1,6) = Sum(5,1,5) + Sum(5,0,5) = 1
  table[1][6] = table[1][5] + table[0][5] = 1 + 0 = 1

But with 1 die having 5 faces, we can't get a sum of 6.
This extra value is removed by checking the if condition-

If (j>f) i.e 6>5
hence, table[1][6] = table[1][6] - table[0][0] = 1-1 = 0

As we traverse through the 2 loops, we will calculate the value of the number of ways and store it in table[i][j] to find further values.
Hence, we will get the final answer for Sum(5,3,8) from table[3][8].
table[3][8] = 18

Therefore, the number of ways to get sum 8 with 3 dice having 5 faces is 18.