Find the number of ways to get the summation of values on each face when all dice thrown. We have N dice with M faces.
source Code
package com.dsacode.Algorithm.dynamic;
import java.math.BigInteger;
public class DiceThrow {
public static int Faces, Throws, Summation;
public static BigInteger Result;
public static BigInteger[][] DPMemo;
public static void main(String args[]) throws Exception {
Faces = 6;
Throws = 6;
Summation = 30;
System.out.println("The number of faces in Dice: " + Faces);
System.out.println("The number of throws: " + Throws);
System.out.println("The Summation of all throws: " + Summation);
DPMemo = new BigInteger[Throws + 1][Summation + 1];
System.out.print("Possibility of dice: " + Solve(Throws, Summation));
System.out.println("/" + new BigInteger(Faces + "").pow(Throws));
}
public static BigInteger Solve(int T, int S) {
if (T < 0 || S < 0)
return BigInteger.ZERO;
else if (T == 0 && S == 0)
return DPMemo[T][S] = BigInteger.ONE;
else if (T == 0 || S == 0)
return DPMemo[T][S] = BigInteger.ZERO;
else if (DPMemo[T][S] != null)
return DPMemo[T][S];
else {
Result = BigInteger.ZERO;
for (int i = 1; i <= Faces; i++)
Result = Result.add(Solve(T - 1, S - i));
return DPMemo[T][S] = Result;
}
}
}
Output
The number of faces in Dice: 6 The number of throws: 6 The Summation of all throws: 30 Possibility of dice: 456/46656
Algorithm Explanation
 | Initialize the values with Faces 6 and Throws 6, Summation with 30. |
| Pass the throws and summation to the utility function. If throw or summation is equal to zero, return zero. |
| Calculate the possibility of dice using dynamic programming and return back to the function. |
| Calculate the number of possibilities using faces power of throws. |
Time Complexity
| Best Case | Average Case | Worst Case |
|---|---|---|
| – | O(m * n * x) | – |