图解LeetCode——剑指 Offer 60. n个骰子的点数

一、题目

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

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

二、示例

2.1> 示例 1:

【输入】 1 【输出】 [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

2.2> 示例 2:

【输入】 2 【输出】 [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制：

• 1 <= n <= 11

三、解题思路

根据题目要求，我们需要获得N个骰子总和点数的概率集合，那么我们就从最简单的1个骰子来看，那么针对一个骰子来说，一共会有从1~6的六个点，并且每个点被投掷出来的概率都是一样的，即：1/6的概率（0.16667）；

那么两个骰子呢？其投掷的总和的值就在从2~12的这11个点（因为一个骰子的点数是从1~6）。那么如何计算其概率呢？我们可以拿两个骰子A和B为例。以骰子A作为基准骰子，以骰子B作为附加值骰子，那么就有如下图规则：

【当投出附加骰子为1点时】

与基准骰子1点的总和为2； 与基准骰子2点的总和为3； 与基准骰子3点的总和为4； 与基准骰子4点的总和为5； 与基准骰子5点的总和为6； 与基准骰子6点的总和为7；

【当投出附加骰子为2点时】

与基准骰子1点的总和为3； 与基准骰子2点的总和为4； 与基准骰子3点的总和为5； 与基准骰子4点的总和为6； 与基准骰子5点的总和为7； 与基准骰子6点的总和为8；

关于投出附加骰子的其他数值，依次类推即可，我就不一一列出来了……

那么如果投掷的骰子是3个呢？即：增加一个骰子C；那么我们也可以将其作为“两个骰子”来计算，即：（骰子A和骰子B的概率）和 骰子C的概率（1/6）。所以，无论是求多少个骰子的总和值概率，我们都可以一步步的将其归化为两个骰子的概率计算方式。下图是两个骰子和三个骰子的概率计算过程：

那么上面介绍完解题思想了之后，我们还是通过示例来加深对这道题的理解。下面我们以两个骰子为例，计算其投掷值总和的概率。具体操作，请见下图所示：

四、代码实现

class Solution {
    public double[] dicesProbability(int n) {
        double[] result = new double[6];
        Arrays.fill(result, 1/6d);
        double[] temp;
        for (int m = 2; m <= n; m++) {
            temp = new double[5 * m + 1];
            for (int i = 0; i < result.length; i++) 
                for (int j = 0; j < 6; j++) 
                    temp[i+j] += result[i] / 6;
            result = temp;
        }
        return result;
    }
}