剑指 Offer 60. n个骰子的点数
把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 <= n <= 11
做题思路：
说实话，这道题是看了k神(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/)的代码和题解才知道怎么做的，先放k神代码吧。
class Solution {
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;
}
}
这是根据K神代码自己加了些注释，希望其他人可以看懂。
class Solution {
public double[] dicesProbability(int n) {
double[] dp = new double[6];
//只有一个骰子时，数组初始化
Arrays.fill(dp, 1.0/6.0);
//骰子的个数进行逐次累加，骰子总数从2开始
for(int i = 2 ;i <= n;i++){
//新数组存放骰子的每个总数和出现的概率
//骰子总数为i时，骰子可能出现的点数i~6i,长度6i-i+1
double[] tmp = new double[5*i+1];
//骰子数为i-1时，所有骰子总数和出现的情况，j值表示数组中的索引，并不表示骰子总数和的数值。
for(int j = 0; j < dp.length; j++){
//新加骰子可能出现的点数1~6,在数组中影响前面索引加0~5的索引指向的值
for(int k = 0;k < 6; k++){
//正向递推，骰子总数为i-1的数组出现的每一个点数和，
//单独拿出来依次和新点数(1~6)相加，计算相加后点数和的概率
tmp[j + k] += dp[j]/6;
}
}
//骰子总数为i的数组赋值骰子总数为i-1的数组
dp = tmp;
}
return dp;
}
}
这位力友大佬力扣 (leetcode-cn.com)的思路更详细点，分享出来，希望有用。
解释思路：
这道题的正向推导其实用概率独立性去解释可能更好理解。
假设有两个骰子A、B，这两个骰子相互独立。
在仅有一个骰子A的情况下，6个点出现的概率都为1/6, 同时A的每个点搭配B的每个点的概率也是相同的，所以骰子A为1会分别乘6个1/6去搭配骰子B的1~6， 即这种搭配2~7的概率分别都为1/36; 骰子A的2也会分别去乘6个1/6去搭配骰子B的1~6, 即这种搭配3~8的概率也分别为1/36, 以此类推。
因为这是独立重复试验，所以之间的关系是相加，所有实验相加后，就得到了最终的结果。
其实本质是高中数学，但是由于加了场景并且要代码实现，所以变难了。
代码：
class Solution {
public double[] dicesProbability(int n) {
//因为最后的结果只与前一个动态转移数组有关，所以这里只需要设置一个一维的动态转移数组
//原本dp[i][j]表示的是前i个骰子的点数之和为j的概率，现在只需要最后的状态的数组，所以就只用一个一维数组dp[j]表示n个骰子下每个结果的概率。
//初始是1个骰子情况下的点数之和情况，就只有6个结果，所以用dp的初始化的size是6个
double[] dp = new double[6];
//只有一个数组
Arrays.fill(dp,1.0/6.0);
//从第2个骰子开始，这里n表示n个骰子，先从第二个的情况算起，然后再逐步求3个、4个···n个的情况
//i表示当总共i个骰子时的结果
for(int i=2;i<=n;i++){
//每次的点数之和范围会有点变化，点数之和的值最大是i*6，最小是i*1，i之前的结果值是不会出现的；
//比如i=3个骰子时，最小就是3了，不可能是2和1，所以点数之和的值的个数是6*i-(i-1)，化简：5*i+1
//当有i个骰子时的点数之和的值数组先假定是temp
double[] temp = new double[5*i+1];
//从i-1个骰子的点数之和的值数组入手，计算i个骰子的点数之和数组的值
//先拿i-1个骰子的点数之和数组的第j个值，它所影响的是i个骰子时的temp[j+k]的值
for(int j=0;j<dp.length;j++){
//比如只有1个骰子时，dp[1]是代表当骰子点数之和为2时的概率，它会对当有2个骰子时的点数之和为3、4、5、6、7、8产生影响，因为当有一个骰子的值为2时，另一个骰子的值可以为1~6，产生的点数之和相应的就是3~8；比如dp[2]代表点数之和为3，它会对有2个骰子时的点数之和为4、5、6、7、8、9产生影响；所以k在这里就是对应着第i个骰子出现时可能出现六种情况，这里可能画一个K神那样的动态规划逆推的图就好理解很多
for(int k=0;k<6;k++){
//这里记得是加上dp数组值与1/6的乘积，1/6是第i个骰子投出某个值的概率
temp[j+k]+=dp[j]*(1.0/6.0);
}
}
//i个骰子的点数之和全都算出来后，要将temp数组移交给dp数组，dp数组就会代表i个骰子时的可能出现的点数之和的概率；用于计算i+1个骰子时的点数之和的概率
dp = temp;
}
return dp;
}
}