algorithm - 概率：如果你有 n 个骰子，每个骰子有 m 个面，就没有获胜的方法

Question

给你若干个骰子 n，每个骰子有若干面 m。你掷出所有 n 个骰子，并记下你掷出每个骰子所掷出的所有骰子的总和。如果你得到一个总和 >= x，你赢了，否则你输了。找出你获胜的概率。

我想生成 1 到 m （大小为 n ）的所有组合，并只计算总和大于 x 的那些组合。方法总数为 m^n

在那之后，它只是两者的分裂。

有没有更好的办法 ？

Answer 1

[编辑：正如 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。

Answer 2

只是为了添加@j_random_hacker 的基本正确答案，当您注意到这一点时，您可以使其更快

f(x, n) = f(x-1, n) - f(xm-1, n-1) + f(x-1, n-1) 如果 x>m+1

这样，您只需花O(1)时间计算每个f值。

Answer 3

//传递 curFace 值将不允许重复组合
//对于 3 个骰子 - 和 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;
}