角色扮演笔纸游戏中骰子概率的动态规划

Question

黑眼是一款流行的幻想角色扮演游戏，在德国相当于地下城和龙。在这个系统中，一个角色有许多属性和天赋。每个天赋都有多个相关属性，为了进行天赋检查，玩家对每个相关属性掷一个d20（20面骰子）。每次掷骰结果超过属性得分时，掷骰和属性之间的差值相加。如果这个差额总和（超出值）大于天赋值，则检查失败。在

本教程的第一个任务是编写一个函数，该函数将与天赋以及天赋等级相关联的属性分数列表作为输入，并返回测试成功的概率。您的算法必须对任意长度的列表有效。

提示：首先编写一个函数来计算超额的概率分布。使用动态规划可以有效地实现这一点。在

---

这是什么意思？我解决了背包问题没有任何重大问题（0/1和无界），但我不知道该怎么办？在

首先要解决的最小问题是排名1，单个属性为12（使用上面的例子）——通过的概率是12/20，对吗？那么2级是13/20，3级是14/20？在

我走对了吗？我觉得我可能误解了实际的游戏规则。在

Answer 1

所以问题是：你可以用属性12，13，12和天赋7掷骰吗。假设你知道第一个骰子的结果，假设是11。然后问题就减少到你可以用属性13和属性12以及天赋7掷骰。现在试试不同的第一次掷骰，假设你第一次掷了14次。你已经结束了2点，所以现在的问题是你可以用属性13和属性12以及天赋5来掷骰。现在试试第一轮20分。现在的问题是在属性13和12以及天赋为-1的情况下，你可以用多少种方式掷骰子（在最后一种情况下显然是0）。在

Answer 2

这里有一点涉及概率和多项式的数学知识。例如，滚动d6可以用多项式表示

x + x^2 + x^3 + x^4 + x^5 + x^6
               -
               6                ,

由于滚动a1的概率为1/6（x/6项），滚动a2的概率为1/6（x^2/6项），等等。滚动d20并计算超过13的超额将是

^{pr2}$

这种表示的意义在于，如果Y是具有多项式p（x）的随机变量，Z是具有多项式q（x）的随机变量，那么Y+Z的多项式就是p（x）q（x）的乘积。例如，将d6多项式乘以它本身，我们得到2d6多项式

x^2 + 2 x^3 + 3 x^4 + 4 x^5 + 5 x^6 + 6 x^7 + 5 x^8 + 4 x^9 + 3 x^10 + 2 x^11 + x^12
                                          
                                         36                                          ,

这应该是正确的分配。在

这里的暴力算法对应于两个线性多项式相乘的firsts outers-inners-lasts（FOIL）规则的广义版本，其中，对于每个多项式因子的每个可能选择项，我们将乘积加到最终和上。这是低效的，因为，例如，如果我们试图通过检查（（1+x）/2）^n来计算n个硬币的头部分布，我们将得到2^n个项的总和。在

本文所指的动态规划算法是计算偏积的较为合理的方法。例如，我们计算（（1+x）/2）^2=（1+2 x+x^2）/4，然后（1+2 x+x^2）/4（1+x）/2=（1+3 x+3 x^2+1）/8，依此类推

Answer 3

对值为k的属性的单掷是一个随机变量，它取0，1，2，3，…，20-k，概率为k/20，1/20，1/20。。。在

您可以将其表示为大小为21-k的数组，其中的概率值为数组中的值。在

如果你有两个（独立）随机变量，X1和X2，那么表示它们总和的随机变量是：

P(X1+X2=n) = sum(i=0 to n)P(X1=i)*P(X2=n-i)

您可以迭代地使用它来计算所有属性滚动总和的分布。然后，您可以通过将最终分布中的概率相加到值S（储蓄滚动值）来找到进行储蓄滚动的概率。在

一个很好的优化方法是不存储任何高于S值的概率，因为它们从未被使用过。这意味着将数组的大小限制为S+1并进行边界检查。在

把所有这些放在一起就得到了这个代码。multiply函数具有复杂度O（len（a1）*len（a2）），但由于a1的长度总是S+1，a2的长度最多为21，所以它具有复杂度O（S）。总的来说，这给了代码复杂度O（nS），其中n是属性的数量。我已经包含了一些针对属性[5，10]的测试运行代码。在

^{pr2}$