《The Dark Eye》是一款流行的奇幻角色扮演游戏，相当于德国版的《龙与地下城》。在这个系统中，角色有许多属性和天赋。每个天赋都有几个与之相关的属性，为了进行天赋检查，玩家需要为每个相关属性投d20(20面骰子)。每次滚动结果超过属性得分时，将滚动和属性之间的差值相加。如果这个差值总和大于天赋值，则检查失败。
本教程的第一个任务是编写一个函数，该函数将与天赋相关的属性分数列表以及天赋排名作为输入，并返回测试成功的概率。你的算法必须对任意长度的列表有效。
提示:首先写一个函数来计算超额的概率分布。这可以使用动态规划有效地完成。
这是什么意思?我解决了背包问题，没有任何重大问题(0/1和无界)，但我不知道该怎么做?
首先要解决的最小问题将是具有单一属性的排名1，例如12(使用上面的示例)-通过的概率将是12/20，对吗?那么排名2是13/20那么排名3是14/20?
我讲对了吗?我觉得我可能误解了游戏规则。
对值为k的属性进行单次掷骰是一个随机变量，它取值为0,1,2,3，…，概率为k/20, 1/20, 1/20，…的20-k
您可以将其表示为大小为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)。总的来说，这使代码的复杂度为0 (n)，其中n是属性的数量。我已经包含了一些针对属性[5,10]的测试运行代码。
def attribute_dist(k):
return [k/20.0] + [1/20.0] * (20-k)
def multiply(a1, a2):
result = [0] * len(a1)
for n in xrange(len(a1)):
for i in xrange(len(a2)):
if 0 <= n - i < len(a1):
result[n] += a1[n-i] * a2[i]
return result
def saving_throw_probability(attributes, S):
d = [1.0] + [0] * S
for a in attributes:
d = multiply(d, attribute_dist(a))
return sum(d)
for i in xrange(30):
print i, saving_throw_probability([5, 10], i)
这里有一些涉及概率和多项式的简洁数学。例如，摇出d6可以用多项式
表示x + x^2 + x^3 + x^4 + x^5 + x^6
-------------------------------
6 ,
因为摇到1的概率是1/6 (x/6项)，摇到2的概率是1/6 (x^2/6项)，等等。滚动d20并计算超过13的多余部分将是
13 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7
------------------------------------------
20 .
这个表示的要点是，如果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 ,
应该被识别为正确的分布。
这里的蛮力算法对应于两个线性多项式相乘的第一-外-内-后(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 + 3 x ^ 2 + 1)/8,等。
所以问题是:在属性为12,13和12，天赋为7的情况下，你有多少种投掷方式?假设你知道第一个骰子的结果，假设是11。然后问题就简化为属性为13和12，天赋为7时你能掷多少次骰子。现在用不同的第一次掷出，假设你第一次掷出的是14。现在的问题是，属性为13和12，天赋为5的情况下，你能掷多少次骰子。现在第一次掷出20个。现在的问题是，在属性为13和12且天赋为-1的情况下(在最后一种情况下显然是0)，你可以掷多少次骰子。