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.
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.
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
//i number of dices available
for(k=1;k<=faces && j>=k;k++)
cout<<"Enter number of dices"<<endl;
cout<<"Enter number of faces in a dice"<<endl;
cout<<"Enter the value of sum"<<endl;
cout<<"Number of ways in which the dices can give the required sum is "<<endl;
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.