Dices Sum
Published:
有意思的动态规划题
Source
- LintCode: (20) Dices Sum
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{align} 6 &= 3(前两次点数之和) + 1(第三次点数) + 2(第四次点数)\\ &= 3(前两次点数之和) + 2(第三次点数) + 1(第四次点数) \end{align}\]就这两种分法而言，不管后两次扔了多少，前两次扔的和为3的分法数都是要计算的，于是这个数就被计算了两次。随着 n 增大，这样重复的计算比比皆是，于是，一个自然的想法就是：自底而上，将前面的结果存起来(比如前两次扔到 3 的分法数之和)，也就是动态规划。
没错，这道题也是典型的DP，鉴于分解数和概率只有一个 \((\frac{1}{6})^n\) 的差别，这里就直接在矩阵中存储概率值了，代码如下：
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的概率，递推公式就是将最后一次掷骰子可能的点数遍历一遍，概率求和：
k1和k2是最后一次掷骰子点数的取值范围，很容易算出。
另外，DP过程中可以发现，求掷i次各个和的概率时，只要用到掷i-1次各个和的概率，掷0 ~ i-2次的结果都用不上，而且纵坐标大于6i的部分都被浪费了。于是，从节省空间的角度，可以将矩阵简化为一个size = 6n的数组，每一轮更新下标为[i, 6i]的部分，即掷i次和为各个值的概率：
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;
}