Dices Sum

Posted on Edited on In
Symbols count in article: 3.6k Reading time ≈ 6 mins.

Source:

Description

Throw n dices, the sum of the dices’ faces is S. Given n, find the all possible value of S along with its probability.

Example:

Example 1:
Input: n = 1
Output: [[1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]
Explanation: Throw a dice, the sum of the numbers facing up may be 1, 2, 3, 4, 5, 6, and the probability of each result is 0.17.

Example 2:
Input: n = 2
Output: [[2,0.03],[3,0.06],[4,0.08],[5,0.11],[6,0.14],[7,0.17],[8,0.14],[9,0.11],[10,0.08],[11,0.06],[12,0.03]]
Explanation: Throw two dices, the sum of the numbers facing up may be in [2,12], and the probability of each result is different.

Analysis & Solution

这道题要求掷n次骰子得到的和为各个值的概率。首先，和的范围是[n, 6n]，返回的结果应当包含其中每个值和对应的概率的键值对。很自然的想法是，将和分解为每次扔骰子的点数，最后和为某个值的概率就是分法数乘上$(\frac{1}{6})^n$。然而，可想而知n一旦变大，分法数增长得可怕。

更重要的是，在操作的过程中，有重复的计算操作。例如，看扔4次和为6的条件下，其中的两种分法：

\begin{equation*}\begin{split}
6 &= 3(前两次点数之和) + 1(第三次点数) + 2(第四次点数)\\
&= 3(前两次点数之和) + 2(第三次点数) + 1(第四次点数)\\
\end{split}\end{equation*}

就这两种分法而言，不管后两次扔了多少，前两次扔的和为3的分法数都是要计算的，于是这个数就被计算了两次。随着n增大，这样重复的计算比比皆是，于是，一个自然的想法就是：自底而上，将前面的结果存起来(比如前两次扔到3的分法数之和)，也就是动态规划。

没错，这道题也是典型的DP，鉴于分解数和概率只有一个$(\frac{1}{6})^n$的差别，这里就直接在矩阵中存储概率值了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
    List<Map.Entry<Integer, Double>> res = new ArrayList();
    double[][] probs = new double[n+1][6*n + 1];

    for (int i = 1; i <= 6; ++i)
        probs[1][i] = 1.0 / 6;

    for (int i = 2; i <= n; ++i) {
        // Throw i times, computing and store probs in tmp
        for (int j = i; j <= 6 * i; ++j) {
            for (int lastDice = Math.max(j - 6*i + 6, 1); lastDice <= Math.min(6, j - i + 1); ++lastDice) {
                // throwing (i-1) times get (i-1) sum at least
                probs[i][j] += probs[i - 1][j - lastDice];
            }
            probs[i][j] /= 6;
        }
    }

    for (int i = n; i <= 6*n; ++i)
      	res.add(new AbstractMap.SimpleEntry<Integer, Double>(i, probs[n][i]));

    return res;
}

probs[i][j]表示掷i次骰子和为j的概率，递推公式就是将最后一次掷骰子可能的点数遍历一遍，概率求和：

$$probs[i][j] = \sum_\limits{k=k_1}^{k_2}probs[i-1][j-k] \times \frac{1}{6}$$

k1和k2是最后一次掷骰子点数的取值范围，很容易算出。

另外，DP过程中可以发现，求掷i次各个和的概率时，只要用到掷i-1次各个和的概率，掷0 ~ i-2次的结果都用不上，而且纵坐标大于6i的部分都被浪费了。于是，从节省空间的角度，可以将矩阵简化为一个size = 6n的数组，每一轮更新下标为[i, 6i]的部分，即掷i次和为各个值的概率：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
    List<Map.Entry<Integer, Double>> res = new ArrayList();
    double[] probs = new double[6*n + 1];
    double[] tmp = new double[6*n + 1];

    for (int i = 1; i <= 6; ++i)
      	probs[i] = 1.0 / 6;

    for (int i = 2; i <= n; ++i) {
        // Throw i times, computing and store probs in tmp
        for (int j = i; j <= 6*i; ++j) {
            // When throwing i times, the prob summing j is stored in tmp[j]
            // throwing (i-1) times and prob summing j is stored in probs[j]
            for (int lastDice = Math.max(j - 6*i + 6, 1); lastDice <= Math.min(6, j - i + 1); ++lastDice) {
                // throwing (i-1) times get (i-1) sum at least
                tmp[j] += probs[j - lastDice];
            }
            tmp[j] /= 6;
        }

        // Transfer probabilities from tmp to probs
        for (int j = i; j <= 6*i; ++j)
            probs[j] = tmp[j];

    }

    for (int i = n; i <= 6*n; ++i)
        res.add(new AbstractMap.SimpleEntry<Integer, Double>(i, probs[i]));

    return res;
}