剑指Offer Java版 面试题60：n个骰子的点数

题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

解法一：基于递归求骰子点数，时间效率不够高

要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有1个；另一堆有n-1个。单独的那一个有可能出现1 ~ 6的点数。我们需要计算1 ~ 6的每一种点数和剩下的n-1个骰子来计算点数和。

接下来把剩下的n-1个骰子仍然分成两堆：第一堆只有1个；第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。

我们可以定义一个长度为6n-n+1的数组，将和为s的点数出现的次数保存到数组的第s-n个元素里。

基于这种思路，我们可以写出如下代码：

private int mMaxValue = 6;

public void printProbability(int number) {
    if (number < 1) {
        return;
    }
    int maxSum = number * mMaxValue;
    int[] probabilities = new int[maxSum - number + 1];
    for (int i = 1; i <= mMaxValue; i++) {
        probability(number, number, i, probabilities);
    }
    double total = Math.pow(mMaxValue, number);
    for (int i = number; i <= maxSum; i++) {
        System.out.printf("%d: %f\n", i, probabilities[i - number] / total);
    }
}

private void probability(int number, int current, int sum, int[] probabilities) {
    if (current == 1) {
        probabilities[sum - number]++;
    } else {
        for (int i = 1; i <= mMaxValue; i++) {
            probability(number, current - 1, i + sum, probabilities);
        }
    }
}

复杂度分析

• 时间复杂度：O(m^n)。
• 空间复杂度：O(mn)。

m为最大点数，n为骰子数。

解法二：基于循环求骰子点数，时间性能好

我们可以考虑用两个数组来存储骰子点数的每个总数出现的次数。

在一轮循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。在下一轮循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一轮循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的次数的总和，所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6个数字之和。

基于这种思路，我们可以写出如下代码：

public void printProbability(int number) {
    if (number < 1) {
        return;
    }
    int[][] probabilities = new int[2][mMaxValue * number + 1];
    for (int i = 1; i <= mMaxValue; i++) {
        probabilities[0][i] = 1;
    }
    int flag = 0;
    for (int k = 2; k <= number; k++) {
        for (int i = 0; i < k; i++) {
            probabilities[1 - flag][i] = 0;
        }
        for (int i = k; i <= mMaxValue * k; i++) {
            probabilities[1 - flag][i] = 0;
            for (int j = 1; j <= i && j <= mMaxValue; j++) {
                probabilities[1 - flag][i] += probabilities[flag][i - j];
            }
        }
        flag = 1 - flag;
    }
    double total = Math.pow(mMaxValue, number);
    for (int i = number; i <= mMaxValue * number; i++) {
        System.out.printf("%d: %f\n", i, probabilities[flag][i] / total);
    }
}

复杂度分析

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)。

m为最大点数，n为骰子数。

👉剑指Offer Java版目录
👉剑指Offer Java版专题