n个骰子的点数

## 1 题目

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

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

**示例 1:**

```txt
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
```

**示例 2:**

```txt
输入: 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

## 2 解题思路

### 2.1 动态规划

#### 2.1.1 问题分析

1. **设输入 $n$ 个骰子的解**（即概率列表）**为 $f(n)$**，**其中点数和 $x$ 的概率为 $f(n, x)$**。
2. **假设已知 $n  - 1$ 个骰子的解 $f(n - 1)$**，**此时添加一枚骰子**，**求 $n$ 个骰子的点数和为 $x$ 的概率 $f(n, x)$**。
3. **当添加骰子的点数为 1 时**，**前 $n - 1$ 个骰子的点数和应为 $x - 1$**，**方可组成点数和 $x$**，**同理**，**当此骰子为 2 时**，**前 $n - 1$ 个骰子应为 $n - 2$**，**以此类推**，**直至此骰子点数为 6**，**将这 6 种情况的概率相加**，**即可得到概率 $f(n, x)$**，**递推公式如下所示**：

$$
   f(n, x) = \sum^6_{x = 1}f(n - 1, x - i) \times \frac16
   $$
4. **根据以上分析**，**得知通过子问题的解 $f(n - 1)$ 可递推计算出 $f(n)$**，**而输入一个骰子的解 $f(1)$ 已知**，**因此可通过解 $f(1)$ 依次递推出任意解 $f(n)$**，如下图所示，为 $n = 2, x = 7$ 的递推计算示意图：

![Picture2.png](/media/202202/2022-02-12_1057170.3733175875882666.png)
5. **观察发现**，**以上递推公式虽然可行**，**但 $f(n - 1, x - i)$ 中的 $x - i$ 会有越界问题**，例如，若希望递推计算 $f(2, 2)$，由于一个骰子的点数和范围为 $[1, 6]$，因此只应求和 $f(1, 1)$，即 $f(1, 0), f(1, -1),..., f(1, -4) $ 皆无意义。
6. **上面的递推公式是逆向的**，**即为了计算 $f(n, x)$**，**将所有与之相关的情况求和**，**而倘若改换为正向的递推公式**，**便可解决问题**，**具体来看**，**由于新增骰子的点数只可能为 1 至 6**，**因此概率 $f(n - 1, x)$ 仅与 $f(n, x + 1), f(n, x + 2),..., f(n, x + 6)$ 相关**，**因而**，**遍历 $f(n + 1)$ 中各点数和的概率**，**并将其相加至 $f(n)$ 中所有相关项**，**即可完成 $f(n - 1)$ 至 $f(n)$ 的递推**。

![Picture3.png](/media/202202/2022-02-12_1106230.40331717078644014.png)
7. 具体实例如下：

![](/media/202202/2022-02-12_1106440.512448934251122.png)

![](/media/202202/2022-02-12_1106520.32350363339285904.png)

![](/media/202202/2022-02-12_1107010.2953053321677126.png)

![](/media/202202/2022-02-12_1107090.5823211622074699.png)

![](/media/202202/2022-02-12_1107170.24416546346844548.png)

![](/media/202202/2022-02-12_1107240.33870643211913043.png)

![](/media/202202/2022-02-12_1107320.398163178063511.png)

![](/media/202202/2022-02-12_1107400.6363814827314325.png)

![](/media/202202/2022-02-12_1107500.07696989614018224.png)

#### 2.1.2 参考代码

```java
/**
 *剑指 Offer 60. n 个骰子的点数
 * @param n 骰子的个数
 * @return  所有骰子朝上一面的点数之和的所有可能的值出现的概率
 */
public double[] dicesProbability(int n) {
    double[] dp = new double[6];
    Arrays.fill(dp, 1.0 / 6.0);
    for (int i = 2; i <= n; i++) {
        double[] tmp = new double[5 * i + 1];
        for (int j = 0; j < dp.length; j++) {
            for (int k = 0; k < 6; k++) {
                tmp[j + k] += dp[j] / 6.0;
            }
        }
        dp = tmp;
    }
    return dp;
}
```

## 参考文献

1. [剑指 Offer 60. n 个骰子的点数](https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof)。
2. [ 剑指 Offer 60. n 个骰子的点数（动态规划，清晰图解）](https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d)。