你会得到n个骰子,每个骰子有m个面。投掷所有n个骰子并记录你从每个骰子中投掷的点数之和。如果你得到的总和>= x,则赢;否则失去。找出你赢得概率。我考虑生成1到m的所有组合(大小为n),并仅计算那些总和大于x的组合数量。总方式数为m^n。然后只需将两者相除即可。是否有更好的方法?
[编辑:如jpalacek所述,时间复杂度是错误的——现在已经修改。]
您可以通过动态规划更有效地解决这个问题,首先将其转化为以下问题:
从n个骰子中至少得到x的方法有多少种?
将其表示为f(x, n)。 然后必须满足以下条件:
f(x, n) = sum(f(x - i, n - 1)) (其中1 <= i <= m)。
即,如果第一个骰子为1,则剩下的n-1个骰子的和必须至少为x-1;如果第一个骰子为2,则剩下的n-1个骰子的和必须至少为x-2;以此类推。
总共有m个术语求和,因此如果记忆化这个函数,它将是O(m^2*n^2),因为最多需要执行此求和工作(m * n)* n次(即每个输入集合一次,假设第一个参数x <= m * n)。
最后一步是获得概率,只需将f(x, n)的结果除以可能的总数,即m^n。
补充一下@j_random_hacker的基本正确答案,你可以注意到当
f(x, n) = f(x-1, n) - f(x-m-1, n-1) + f(x-1, n-1) 如果 x>m+1
这样,您只需要花费O(1)
的时间来计算每个f
值即可。
//传递curFace值将禁止重复组合
//对于三个骰子-和为8-2 4 2和2 2 4是相同的组合-因此应被视为一个计数
int sums(int totSum,int noDices,int mFaces,int curFace,HashMap<String,Integer> map)
{
int count=0;
if (noDices<=0 || totSum<=0)
return 0;
if (noDices==1)
{
if (totSum>=1 & totSum<=mFaces)
return 1;
else
return 0;
}
if (map.containsKey(noDices+"-"+totSum))
return map.get(noDices+"-"+totSum);
for (int i=curFace;i<=mFaces;i++)
{
count+=sums(totSum-i,noDices-1,mFaces,i,map);
}
map.put(noDices+"-" +totSum,count);
return count;
}
f(x,n)
,您需要计算超过m*n
个函数值(实际上大约需要计算x*n
个,但肯定不止这些)。因此,最终结果会近似于O(x*n*m)
。 - jpalecek