I have a problem to solve where we have n number of dice, each with 6 faces. I need to print all possible combinations for which the sum of the face-up numbers equals target.
for example: if n=2, target=10, then I need to print (4,6), (6,4), (5,5)

I was able to get to solve this with the below code but I want a more optimized solution using dynamic programming. Also, I was not sure how to calculate the time complexity for the below code, please help me to find the time complexity (Big O notation) of the below code and also help me to optimize and reduce the time complexity of this code using dynamic programming and memoization

public class Test {
    public static void main(String[] args) {
        int numDie = 2;
        int target = 10;
        int sides = 6;
        printTargetSumCombination(numDie, target, sides, new ArrayList<>());
    }

    private static void printTargetSumCombination(int numDie, int target, int sides, List<Integer> chosen) {
        if (numDie == 0) {
            if(chosen.stream().mapToInt(Integer::intValue).sum()==target)
                System.out.println(chosen);
        } else {
            for (int i = 1; i <= sides; i  ) {
                chosen.add(i);
                printTargetSumCombination(numDie - 1, target, sides, chosen);
                chosen.remove(chosen.size() - 1);
            }
        }
    }
}

CodePudding user response：

Here is a DP implementation.

The idea is: to solve the problem with n dice and target t, you can:

• Take the first die and consider all its possible values
• For every value v, consider the subproblem consisting of n - 1 dice and target t - v
• Combine v with the solutions of the subproblem

When a problem (n, t) is solved, its solutions are stored in a map (memoization).

import java.util.*;

public class DiceSolver
{
    private int sides;
    private HashMap<String, List<int[]>> cache;

    public DiceSolver(int sides)
    {
        this.sides = sides;
        cache = new HashMap<String, List<int[]>>();
    }

    public List<int[]> getSolutions(int numDice, int target)
    {
        // No need to compute anything if the target is out of reach
        if(target < numDice || target > sides * numDice)
            return Collections.emptyList();

        String key = numDice   "|"   target;
        List<int[]> solutions = cache.get(key);
        if(solutions==null)
        {
            // Compute the solutions and store them in the cache
            solutions = computeSolutions(numDice, target);
            cache.put(key, solutions);
        }
        return solutions;
    }

    private List<int[]> computeSolutions(int numDice, int target)
    {
        if(numDice > 1)
        {
            List<int[]> solutions = new ArrayList<int[]>();
            for(int v=1;v<=sides;v  )
            {
                // Combine the first die with the solutions of the subproblem
                for(int[] sol : getSolutions(numDice - 1, target - v))
                    solutions.add(prepend(v, sol));
            }
            return solutions;
        }
        else
        {
            // 1-die problem
            return Collections.singletonList(new int[]{target});
        }
    }

    private static int[] prepend(int val, int[] arr)
    {
        int[] res = new int[arr.length   1];
        res[0] = val;
        System.arraycopy(arr, 0, res, 1, arr.length);
        return res;
    }

    public static void main(String[] args) 
    {
        DiceSolver solver = new DiceSolver(6);
        List<int[]> solutions = solver.getSolutions(2, 10);
        solutions.forEach(sol -> System.out.println(Arrays.toString(sol)));
    }
}

Output:

[4, 6]
[5, 5]
[6, 4]

CodePudding user response：

Below is an option to optimize your function. The approach is similar to yours, but it includes the additional condition, which stops the recursion if the branch can't lead to any correct solutions. This significantly reduces number of required iterations. With numbers from your example the iteraton count decreases from 43 to 7. I'm not sure about the O complexity, it depends on the input, but with some tests I see the number of iterations is proportional to the nr of solutions, so I'd assume it's O(n)

public class Dice {
    static final int target = 10;
    static final int diceCount = 2;
    static final int sides = 6;
    static int iterations = 0;
    static int validIterations = 0;

    public static void main(String[] args) {
        scorePrinter(sides, diceCount, new ArrayList<>());
        System.out.println("Iterations nr: "   iterations);
        System.out.println("Valid combinations: "   validIterations);
    }

    static int scorePrinter(int sides, int dice, List<Integer> scores) {
        int scoresSum = scores.stream().reduce(0, Integer::sum);
        if (dice == 0 && scoresSum == target) {
            System.out.println(scores);
            validIterations  ;
            return iterations  ;
        }
        else if (dice == 0) {
            return iterations  ;
        }
        else {
            for (int i = 1; i < sides   1; i  ) {
                if ((dice - 1 <= (target - scoresSum - i)) && ((sides * (dice - 1)) >= target - scoresSum - i))
                    scorePrinter(sides, dice - 1, Stream.concat(scores.stream(), Stream.of(i)).collect(Collectors.toList()));
            }
            return iterations  ;
        }
    }
}