Dice Throw Problem - Sanfoundry

This is a C++ Program that Solves Dice Throw Problem using Dynamic Programming technique.

Problem Description

There are n identical dices. Each dice has given number of faces. In how many ways, you can get the given sum.

Problem Solution

Create a matrix to store results and start calculating the results in a bottom up fashion.

Expected Input and Output

Case-1:

 
n=2
sum=4
faces=3 
No. of ways=3 (1+3,2+2,3+1)

Program/Source Code

Here is source code of the C++ Program to Solve Dice Throw Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<vector>
```
```
using namespace std;
```
```
 
```

int diceThrow(int n, int faces, int sum)

```
{
```
```
    //matrix to caching results
```

    vector<vector<int> > dp(n+1,vector<int>(sum+1,0));

```
 
```

    //dp[i][j]=number of ways to get sum j with i number of available dices

```
 
```
```
    int i,j,k;
```
```
 
```
```
    //initialization
```
```
    dp[0][0]=1;
```
```
 
```
```
    //i number of dices available
```
```
    for(i=1;i<=n;i++)
```
```
    {
```
```
        //sum j
```
```
        for(j=1;j<=sum;j++)
```
```
        {
```
```
            if(j<i)
```
```
                dp[i][j]=0;
```
```
 
```
```
            else if(j>faces*i)
```
```
                dp[i][j]=0;
```
```
 
```
```
            else
```
```
            {
```

                for(k=1;k<=faces && j>=k;k++)

                    dp[i][j]+=dp[i-1][j-k];

```
            }
```
```
 
```
```
        }
```
```
    }
```
```
 
```
```
    return dp[n][sum];
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```
```
    int faces;
```
```
    int sum;
```
```
 
```

    cout<<"Enter number of dices"<<endl;

```
    cin>>n;
```
```
 
```

    cout<<"Enter number of faces in a dice"<<endl;

```
    cin>>faces;
```
```
 
```

    cout<<"Enter the value of sum"<<endl;

```
    cin>>sum;
```
```
 
```

    cout<<"Number of ways in which the dices can give the required sum is "<<endl;

```
    cout<<diceThrow(n,faces,sum);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the value for number of dices and number of faces in a dice. We pass these values to the function diceThrow as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ dice_throw_problem.cpp
$ ./a.out
Enter number of dices
3
Enter number of faces in a dice
4
Enter the value of sum
5
Number of ways in which the dices can give the required sum is 
6

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you find any mistake above, kindly email to [email protected]

« Prev - Stolen Values Problem using Dynamic Programming

» Next - Boolean Parenthesization Problem using Dynamic Programming

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Check Programming Books
Check Computer Science Books
Apply for Computer Science Internship

Recommended Articles: