Pet*_*ter 4 algorithm math probability
给你一些骰子,每个都有许多面m.你滚动所有的骰子并记下你掷出每个骰子所得到的所有投掷的总和.如果你得到一个总和> = x,你就赢了,否则就输了.找出你赢的概率.
我想过生成1到m(大小为n)的所有组合,并且只保留那些总和大于x的组合.总路数为m ^ n
在那之后它只是两者的分歧.
有没有更好的办法 ？
[编辑:正如jpalacek所说,时间复杂性是错误的 - 我现在已经解决了这个问题.]
您可以通过动态编程更有效地解决这个问题,首先将其更改为问题:
有多少种方法可以从n个骰子得到至少x？
将其表示为f(x,n).那一定是那样的
对于所有1 <= i <= m,f(x,n)= sum(f(x-i,n-1)).
即如果第一个骰子有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.