AlgoPressAppearance
60-n个骰子的点数
题目描述
https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof
把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
思路：组合
组合，dfs枚举每个骰子出现的次数，放入到hash表中。
最后再统计出每种情况出现的概率。
实现代码
csharp
public class Solution {
Dictionary<int, int> dict;
int total = 0;
private int getSum(int[] bits){
int sum = 0;
for(int i=0; i<bits.Length; i++){
sum+=bits[i];
}
return sum;
}
private void dfs(int index, int[] bits){
if(index == bits.Length){
//循环结束
int key = getSum(bits);
if(!dict.ContainsKey(key)){
dict.Add(key,1);
}
else{
dict[key]++;
}
total++;
return;
}
for(int i=1; i<=6; i++){
bits[index] = i;
dfs(index+1,bits);
}
}
public double[] DicesProbability(int n) {
dict = new Dictionary<int, int>();
int[] bits = new int[n];
dfs(0,bits);
//输出
double[] result = new double[dict.Keys.Count];
int index = 0;
foreach(int key in dict.Keys)
{
Console.WriteLine("key{0},index{1}",key,index);
result[index] = (double) dict[key] / total;
index++;
}
return result;
}
}
优化回溯 个数可以提前得知，每一份的数据也可以提前得知
1个筛子，出点数是 1 - 6, 两个骰子，最小是 2 最大是 6 * 2， 三个骰子最小是3，最大是 6 * 3. 所以最大的个数已经确定，即 count = 6 * n - n + 1
点数组合的总数就是 6^n ，即 1个骰子就是6种组合， 再来一个骰子就是 6 * 6 ，再来一个骰子就是 6 * 6 * 6
csharp
public class Solution {
int curSum = 0;
int count = 0;
int total = 1;
double[] result ;
private void dfs(int index, int n){
if(index == n){
result[curSum-n] += 1.0 / total;
return;
}
for(int i=1; i<=6; i++){
curSum+=i;
dfs(index+1,n);
curSum-=i;
}
}
public double[] DicesProbability(int n) {
count = 6*n - n + 1;
for(int i=0;i<n;i++){
total *=6;
}
result = new double[count];
dfs(0,n);
return result;
}
}
思路2：动态规划
csharp
public class Solution {
public double[] DicesProbability(int n){
double[] dp = new double[6];
Array.Fill(dp,1.0/6.0);
for(int i=2; i<=n; i++){
double[] tmp = new double[6 * i - i + 1]; //总情况数
for(int j=0; j<dp.Length; j++){
for(int k=0; k<6; k++){
tmp[j+k] += dp[j] / 6.0; //每种组合的概率都是前面的概率 * 1/6 ，但是和相同的会累计，比如 2,3 和 3,2的概率会累计到一起
}
}
dp = tmp;
}
return dp;
}
}
复习:20220509
csharp
public class Solution {
public double[] DicesProbability(int n) {
double[] dp = new double[6]; //初始化概率
Array.Fill(dp,1.0/6.0);
for(int i=2; i<=n; i++){
int count = 5 * i + 1;
double[] dp2 = new double[count];
for(int j=0; j<dp.Length; j++){
for(int k=0; k<6; k++){
dp2[j+k] += dp[j] / 6.0;
}
}
dp = dp2;
}
return dp;
}
}