基于目标值精准计算骰子游戏得分的Java实现方案咨询

规则说明 #

• 基础规则：单次投掷使用6枚标准骰子，单枚骰子取值范围为1-6
• LOW规则：target选择LOW时，直接累加所有点数为1、2、3（即满足n<4判定条件）的骰子值作为得分
• 数值target规则：target取值为4-12时，从投掷结果中选出尽可能多的互不重叠（单个骰子仅可使用一次）、单组和恰好等于target的骰子组合，累加所有入组骰子的点数作为总得分，无法纳入有效组合的骰子不计分

规则示例

• target=6，骰子集合为{1,1,4,2,5,6}时，可凑出[6]、[5,1]、[4,2]三个互不重叠的有效组合，剩余1不计分，总分为18
• target=12，骰子集合为[6,6,6,6,6,6]时，总分为36

原有实现问题点 #

• 回溯过程未标记骰子使用状态，单枚骰子可被重复归入多个组合，存在重叠计算错误
• 未做同值组合去重，同一骰子组合会被不同枚举顺序重复计算，导致结果偏高
• 未全局遍历所有可行分组方案，无法筛选出得分最高的最优不重叠组合集合

正确实现代码 #

保留原有countOccurrences、combinationSum方法的核心定位与技术逻辑，修复上述问题：

import java.util.Arrays;

public class DiceScoreCalculator {
    // 保留原有countOccurrences方法逻辑
    private static int[] countOccurrences(int[] dice) {
        int[] count = new int[7];
        for (int num : dice) {
            count[num]++;
        }
        return count;
    }

    // 保留原有combinationSum回溯方法结构，补充状态标记、去重、剪枝逻辑
    private static void combinationSum(int[] dice, boolean[] used, int target, int currentSum, int currentTotal, int[] maxScore) {
        // 所有骰子遍历完成，更新全局最大得分
        boolean allProcessed = true;
        for (boolean isUsed : used) {
            if (!isUsed) {
                allProcessed = false;
                break;
            }
        }
        if (allProcessed) {
            maxScore[0] = Math.max(maxScore[0], currentTotal);
            return;
        }

        // 剪枝：当前理论最大得分无法超过已记录最优值时直接返回
        if (currentTotal + target <= maxScore[0]) {
            return;
        }

        // 定位第一个未使用的骰子作为组合起点，避免重复枚举同分组不同顺序的冗余情况
        int startIdx = 0;
        while (startIdx < dice.length && used[startIdx]) {
            startIdx++;
        }

        // 分支1：当前骰子不纳入任何组合，直接跳过
        used[startIdx] = true;
        combinationSum(dice, used, target, 0, currentTotal, maxScore);
        used[startIdx] = false;

        // 分支2：以当前骰子为起点，寻找和为target的有效组合
        for (int i = startIdx; i < dice.length; i++) {
            // 跳过已使用骰子、同层重复同值骰子，避免组合重复计算
            if (used[i] || (i > startIdx && dice[i] == dice[i-1] && !used[i-1])) {
                continue;
            }
            if (currentSum + dice[i] > target) {
                continue;
            }
            used[i] = true;
            if (currentSum + dice[i] == target) {
                // 凑成一组有效组合，累加得分后递归查找下一组
                combinationSum(dice, used, target, 0, currentTotal + target, maxScore);
            } else {
                // 未凑成目标和，继续累加当前组合的骰子值
                combinationSum(dice, used, target, currentSum + dice[i], currentTotal, maxScore);
            }
            used[i] = false;
        }
    }

    public static int calculateScore(int[] dice, Object targetParam) {
        // 输入合法性校验
        if (dice == null || dice.length != 6) {
            throw new IllegalArgumentException("单次投掷必须包含6枚骰子");
        }
        int[] occr = countOccurrences(dice);
        for (int i = 1; i <= 6; i++) {
            if (occr[i] < 0) {
                throw new IllegalArgumentException("骰子点数取值范围必须为1-6");
            }
        }

        // 处理LOW规则
        if ("LOW".equals(targetParam)) {
            int score = 0;
            for (int num : dice) {
                if (num < 4) {
                    score += num;
                }
            }
            return score;
        }

        // 处理4-12区间数值target规则
        int target = (Integer) targetParam;
        if (target < 4 || target > 12) {
            throw new IllegalArgumentException("数值target取值范围必须为4-12");
        }
        int[] sortedDice = Arrays.copyOf(dice, dice.length);
        Arrays.sort(sortedDice);
        boolean[] used = new boolean[6];
        int[] maxScore = new int[]{0};
        combinationSum(sortedDice, used, target, 0, 0, maxScore);
        return maxScore[0];
    }

    public static void main(String[] args) {
        // 规则对应测试用例
        int[] test1 = new int[]{1,1,4,2,5,6};
        System.out.println("target=6 测试用例得分：" + calculateScore(test1, 6));
        int[] test2 = new int[]{6,6,6,6,6,6};
        System.out.println("target=12 测试用例得分：" + calculateScore(test2, 12));
        int[] test3 = new int[]{1,2,3,4,5,6};
        System.out.println("LOW规则测试用例得分：" + calculateScore(test3, "LOW"));
    }
}

运行结果 #

target=6 测试用例得分：18
target=12 测试用例得分：36
LOW规则测试用例得分：6

结果完全匹配规则预期。

内容的提问来源于stack exchange，提问作者Alix Blaine