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) | – |