# Dice Throw Problem – Dynamic Programming Solutions

«
»

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
1. `#include<iostream>`
2. `#include<vector>`
3. `using namespace std;`
4. ` `
5. `int diceThrow(int n, int faces, int sum)`
6. `{`
7. `    //matrix to caching results`
8. `    vector<vector<int> > dp(n+1,vector<int>(sum+1,0));`
9. ` `
10. `    //dp[i][j]=number of ways to get sum j with i number of available dices`
11. ` `
12. `    int i,j,k;`
13. ` `
14. `    //initialization`
15. `    dp[0][0]=1;`
16. ` `
17. `    //i number of dices available`
18. `    for(i=1;i<=n;i++)`
19. `    {`
20. `        //sum j`
21. `        for(j=1;j<=sum;j++)`
22. `        {`
23. `            if(j<i)`
24. `                dp[i][j]=0;`
25. ` `
26. `            else if(j>faces*i)`
27. `                dp[i][j]=0;`
28. ` `
29. `            else`
30. `            {`
31. `                for(k=1;k<=faces && j>=k;k++)`
32. `                    dp[i][j]+=dp[i-1][j-k];`
33. `            }`
34. ` `
35. `        }`
36. `    }`
37. ` `
38. `    return dp[n][sum];`
39. ` `
40. `}`
41. ` `
42. `int main()`
43. `{`
44. `    int n;`
45. `    int faces;`
46. `    int sum;`
47. ` `
48. `    cout<<"Enter number of dices"<<endl;`
49. `    cin>>n;`
50. ` `
51. `    cout<<"Enter number of faces in a dice"<<endl;`
52. `    cin>>faces;`
53. ` `
54. `    cout<<"Enter the value of sum"<<endl;`
55. `    cin>>sum;`
56. ` `
57. `    cout<<"Number of ways in which the dices can give the required sum is "<<endl;`
58. `    cout<<diceThrow(n,faces,sum);`
59. ` `
60. `    cout<<endl;`
61. `    return 0;`
62. `}`
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.

Take Data Structure I Mock Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10