题目：把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印出 s 的所有可能的值出现的概率。
练习地址
https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
解法一：基于递归求骰子点数，时间效率不够高
要想求出 n 个骰子的点数和，可以先把 n 个骰子分为两堆：第一堆只有 1 个；另一堆有 n-1 个。单独的那一个有可能出现 1 ~ 6 的点数。我们需要计算 1 ~ 6 的每一种点数和剩下的 n-1 个骰子来计算点数和。
接下来把剩下的 n-1 个骰子仍然分成两堆：第一堆只有 1 个；第二堆有 n-2 个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的 n-2 个骰子来计算点数和。
我们可以定义一个长度为 6n-n+1 的数组，将和为 s 的点数出现的次数保存到数组的第 s-n 个元素里。
基于这种思路，我们可以写出如下代码：
private int mMaxValue = 6;
public void printProbability(int number) {
if (number < 1) {
return;
}
int maxSum = number * mMaxValue;
int[] probabilities = new int[maxSum - number + 1];
for (int i = 1; i <= mMaxValue; i++) {
probability(number, number, i, probabilities);
}
double total = Math.pow(mMaxValue, number);
for (int i = number; i <= maxSum; i++) {
System.out.printf("%d: %f\n", i, probabilities[i - number] / total);
}
}
private void probability(int number, int current, int sum, int[] probabilities) {
if (current == 1) {
probabilities[sum - number]++;
} else {
for (int i = 1; i <= mMaxValue; i++) {
probability(number, current - 1, i + sum, probabilities);
}
}
}
复杂度分析
- 时间复杂度：O(m^n)。
- 空间复杂度：O(mn)。
m 为最大点数，n 为骰子数。
解法二：基于循环求骰子点数，时间性能好
我们可以考虑用两个数组来存储骰子点数的每个总数出现的次数。
在一轮循环中，第一个数组中的第 n 个数字表示骰子和为 n 出现的概率。在下一轮循环中，我们加上一个新的骰子，此时和为 n 的骰子出现的概率应该等于上一轮循环中骰子点数和为 n-1、n-2、n-3、n-4、n-5 与 n-6 的概率的总和除以 6，所以我们把另一个数组的第 n 个数字设为前一个数组对应的第 n-1、n-2、n-3、n-4、n-5 与 n-6 个数字除 6 之和。
基于这种思路，我们可以写出如下代码：
class Solution {
public double[] dicesProbability(int n) {
double[] dp = new double[6];
Arrays.fill(dp, 1 / 6.0);
for (int i = 2; i <= n; i++) {
double[] temp = new double[5 * i + 1];
for (int j = 0; j < dp.length; j++) {
for (int k = 0; k < 6; k++) {
temp[j + k] += dp[j] / 6;
}
}
dp = temp;
}
return dp;
}
}
复杂度分析
- 时间复杂度：O(n^2)。
- 空间复杂度：O(n)。
