使用动态规划打印目标总和的所有骰子组合

Question

我有一个问题要解决，我们有 n 个骰子，每个骰子有 6 个面。我需要打印所有可能的组合，其中面朝上数字的总和等于目标。
例如：如果 n=2, target=10，那么我需要打印 (4,6), (6,4), (5,5)

我能够使用下面的代码解决这个问题，但我想要一个使用动态编程的更优化的解决方案。另外，我不确定如何计算下面代码的时间复杂度，请帮助我找到下面代码的时间复杂度（大 O 表示法），并帮助我使用动态优化和降低这段代码的时间复杂度编程和记忆

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);
            }
        }
    }
}

Answer 1

以下是优化您的功能的选项。该方法与您的方法类似，但它包括附加条件，如果分支不能导致任何正确的解决方案，则该条件将停止递归。这显着减少了所需的迭代次数。使用您示例中的数字，迭代计数从 43 减少到 7。我不确定 O 的复杂性，它取决于输入，但通过一些测试，我看到迭代次数与解决方案的 nr 成正比，所以我假设它是 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++;
        }
    }
}

Answer 2

这是一个 DP 实现。

思路是：用n个骰子和目标t解决问题，你可以：

取第一个骰子并考虑其所有可能的值
对于每个值 v，考虑由 n - 1 骰子和目标 t - v
结合v子问题的解

解决问题（n、t）后，其解决方案将存储在地图中（记忆）。

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)));
    }
}

输出：

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

使用动态规划打印目标总和的所有骰子组合

Printing all dice combinations for a target sum using dynamic programming

java

algorithm

memoization

dynamic-programming

dice