This is a C++ Program that Solves Dice Throw Problem using Dynamic Programming technique.
There are n identical dices. Each dice has given number of faces. In how many ways, you can get the given sum.
Create a matrix to store results and start calculating the results in a bottom up fashion.
Case-1:
n=2 sum=4 faces=3 No. of ways=3 (1+3,2+2,3+1)
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;
}
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.
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.
- Check Programming Books
- Check Computer Science Books
- Check Data Structure Books
- Practice Design & Analysis of Algorithms MCQ
- Apply for Computer Science Internship