Dynamic programming

Dice Throw Problem

Pinterest LinkedIn Tumblr

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 CaseAverage CaseWorst Case
O(m * n * x)

Reference

  1. http://www.cs.ru.ac.za/research/groups/vrsig/pastprojects/040learning/paper02.pdf
  2. https://tkramesh.wordpress.com/2011/04/17/dynamic-programming-probability-gambling-and-a-die/

Write A Comment