剑指 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
方法一： 回溯算法暴力枚举
private int[] count;
public double[] dicesProbability(int n) {
count = new int[6 * n + 1];
// 回溯算法枚举所有情况
backtrack(n, 0, 0);
int kind = (int) Math.pow(6, n);
// 所有可能出现的值的个数是 6 * n - n = 5 * n;
double[] res = new double[5 * n + 1];
for(int i = n; i < count.length; i++) {
res[i-n] = count[i] * 1.0 / kind;
}
return res;
}
public void backtrack(int n, int index, int sum) {
// 递归出口
if (index == n) {
// 将当前值出现的个数+1
count[sum]++;
return;
}
for(int i = 1; i <= 6; i++) {
// 依次将当前骰子设置为1, 2, 3 ... 6, 然后递归后边的骰子
backtrack(n, index + 1, sum + i);
}
}
方法二： 动态规划算法
使用数组int[] dp = new int[n * 6 + 1];dp[i]的值表示为记录n个骰子的值之和i出现的次数。
其中N个骰子的值的范围[N, 6*N], 而当前的点数i可以通过在前N-1个骰子里点数i-1, i-2, i-3... i - 6出现的次数之和计算出来。
比如在只有一个骰子时, 1, 2, 3... 6, 分别只出现1次。
当需要计算两个骰子时, 两个是骰子的点数范围是(2, 12);
那么点数12的次数是上一轮11, 10, 9, 8, 7, 6出现的次数之和
接着计算点数11出现的次数 , 他是上一轮 10, 9, 8, 7, 6, 5 出现的次数
...
接着计算点数6出现的次数, 他是上一轮 5, 4, 3, 2, 1, 0 出现的次数之和。
接着计算点数5出现的次数, 他是上一轮 4, 3, 2, 1, 0, -1 出现的次数之和。
基本思路就比较清晰了。现在提个问题, 我可不可以先计算6, 然后依次计算7,8,9...12出现的个数吗？这个计算的顺序是不是只能倒着计算？
答案是： 必须倒着计算。原因是假如是先计算的6, 那么后面我计算7的时候, 我需要的是上一轮的总和为6的次数, 你如果先计算6, 则DP[6]已经修改为本轮的6出现的次数了, 与我需要的上一轮的数就不相符了。
public double[] dicesProbability(int n) {
int[] dp = new int[n * 6 + 1];
for(int i = 1; i <= 6; i++) {
dp[i] = 1;
}
for(int i = 2; i <= n; i++) {
// i 个骰子的值的范围是 [i, 6*i]
for(int j = i*6; j >= i; j--) {
// 重置dp[j]的值, 因为dp[j]之前被计算过, 我们并不关心当前j这个值在上一次轮出现的次数是多少
// 我们只想知道 j-1, j-2... j-6 在上一轮出现的次数
dp[j] = 0;
for(int k = 1; k <= 6; k++) {
// j-k是上一轮的数, 其值最小为i-1
// 从我上面的示例也知道j-K是有可能小于上一轮数组的最小值的,
// 小于则说明上一轮的值已经全部遍历完了
if (j-k < i-1) {
break;
}
dp[j] += dp[j-k];
}
}
}
int all = (int) Math.pow(6, n);
double[] res = new double[5 * n + 1];
for(int i = n; i < dp.length; i++) {
res[i-n] = (dp[i] * 1.0) / all;
}
return res;
}