Problem: Given N dices. Each dice has A faces. Find the total number of ways these dices can make sum S when all are thrown together.
// the below code is written in C++.
#include<bits/stdc++.h> using namespace std; int main() { int s=10; // This is the required Sum we want to generate int n=5; // n is total number of dices. int A=6;
// A is number of faces each dice has. Each face has one unique number from 1 to A.
int i,j,k; // d[i][j] depicts number of ways i dices can make sum of j. long long int d[n+1][s+1]; // setting no. of ways for one dice to make sum 1 to A as 1. for(i=1;i<=A;i++) { d[1][i]=1; } // after A, no. of ways is 0. for(i=A+1;i<=s;i++) { d[1][i]=0; } // setting no. of ways for all dices to make sum 0 as 0. for(i=1;i<=n;i++) d[i][0]=0; for(i=2;i<=n;i++) // for i no. of dices. { for(j=1;j<=s;j++) // for sum j. { long long int cnt=0; for(k=1;k<=A;k++) // for each face. { if(j-k>=0) {// taking k for i-th dice and taking rest j-k for other (i-1) dices. cnt+=d[i-1][j-k]; } } d[i][j]=cnt; } }
cout<<"no. of ways : "<<d[n][s]<<endl; return 0; }
Complexities :
Time complexity: O(N*S*A)
Space complexity: O(N*S)