题目描述
把 n 个骰⼦扔在地上，所有骰⼦朝上⼀⾯的点数之和为 s 。输⼊ n ，打印出 s 的所有可能的值出现的概率。
你需要⽤⼀个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰⼦所能掷出的点数集合中第 i ⼩的那个的概率。
示例1：
输⼊: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例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 - 6 的概率都是 1/6，如果有 n 个 骰⼦，先不看重复的情况，⼀共有 $6^n$ 种情况，点数的范围是 n ~ 6n ，也就是 5n+1 种。
但是以上的计算复杂度实在太⾼，我们不能接受。
其实，这道题可以⽤动态规划来处理， 1 个骰⼦的情况是已知的，⽽ 2 个骰⼦的情况呢？ 2 个骰⼦的情况，可以使⽤ 1 个骰⼦的情况推出， 3 个骰⼦的情况，可以使⽤ 2 个骰⼦的结果推出...
假设n个骰⼦的解释f(n)，n个骰⼦扔出点数和为x的概率为f(n,x)
假设我们已经计算出 n-1 个骰⼦扔出的点数和以及概率 f(n-1)，现在加⼀个骰⼦，⼀共有 n 个骰⼦，f(n) 怎么求呢？
我们现在就只求 f(n,x) :
- 如果第 n 个骰⼦扔出的是 1 ，那么剩下的 n-1 个骰⼦扔出的应该是 x-1 ,概率为 f(n-1,x-1)
- 如果第 n 个骰⼦扔出的是 2 ，那么剩下的 n-1 个骰⼦扔出的应该是 x-2 ,概率为 f(n-1,x-2)
- 如果第 n 个骰⼦扔出的是 3 ，那么剩下的 n-1 个骰⼦扔出的应该是 x-3 ,概率为 f(n-1,x-3)
- 如果第 n 个骰⼦扔出的是 4 ，那么剩下的 n-1 个骰⼦扔出的应该是 x-4 ,概率为 f(n-1,x-4)
- 如果第 n 个骰⼦扔出的是 5 ，那么剩下的 n-1 个骰⼦扔出的应该是 x-5 ,概率为 f(n-1,x-5)
- 如果第 n 个骰⼦扔出的是 6 ，那么剩下的 n-1 个骰⼦扔出的应该是 x-6 ,概率为 f(n-1,x-6)
所以， f(n,x) 应该是上⾯的概率加起来， f(n,x) = (f(n-1,x-1)+ f(n-1,x-2) +f(n-1,x-
3)+f(n-1,x-4)+f(n-1,x-5)+f(n-1,x-6) ) * 1/6。注意，最后⼀个骰⼦扔出每⼀种的概率都是1/6。
那么我们的程序应该是从 1 个骰⼦模拟增加到 n 个骰⼦，不断计算出概率。
class Solution {
public double[] nTou(int n) {
double pre[] = {1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d};
for (int i = 2; i <= n; i++) {
double temple[] = new double[5 * i + 1];
for (int j = 0; j < pre.length; j++){
for (int x = 0; x < 6; x++){
temple[j + x] += pre[j] / 6;
}
}
pre = temple;
}
return pre;
}
}