概率：如果你有n个每个面有m个点数的骰子，获胜的方法数量为多少。

Question

你会得到n个骰子，每个骰子有m个面。投掷所有n个骰子并记录你从每个骰子中投掷的点数之和。如果你得到的总和>= x，则赢；否则失去。找出你赢得概率。我考虑生成1到m的所有组合（大小为n），并仅计算那些总和大于x的组合数量。总方式数为m^n。然后只需将两者相除即可。是否有更好的方法？

- Peter

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。

- j_random_hacker

---

您的分析有一点问题：为了计算 f(x,n)，您需要计算超过m*n个函数值（实际上大约需要计算x*n个，但肯定不止这些）。因此，最终结果会近似于 O(x*n*m)。 - jpalecek

@jpalecek：很好的发现，感谢。 假设 x <= n*m（因为否则答案显然为0），O(m^2 * n^2)的限制应该没问题 - 我会更新答案。 - j_random_hacker

Answer 2

补充一下@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值即可。

- jpalecek

---

非常好，+1！在它变得清晰之前，必须盯着它看一会儿：我给出的总和中的所有术语都与先前的x值计算共享，除了第一个和最后一个，因此只需分别减去并添加它们。 - j_random_hacker

Answer 3

//传递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;
}

- DJ'

---

我正在努力理解你的回答。为什么你想把“curFace”作为函数参数添加进去，当你并不知道初始的“curFace”是什么呢？抱歉，我刚刚才发现这个问题，目前正在手机上打字。 - Zeid Tisnes