角色扮演纸笔游戏中骰子概率的动态规划
《黑暗之眼》是一款非常受欢迎的奇幻角色扮演游戏，类似于《龙与地下城》。在这个系统中，每个角色都有一些属性和才能。每个才能都有几个相关的属性，玩家在进行才能检定时，需要为每个相关属性掷一个20面骰子（d20）。每次掷骰子的结果如果超过了属性分数，掷骰结果和属性分数之间的差值会被累加起来。如果这个差值总和（也就是超出的部分）大于才能值，那么检定就失败了。
在这个教程中，你的第一个任务是编写一个函数，输入一个与才能相关的属性分数列表和才能等级，然后返回测试成功的概率。你的算法必须能够高效处理任意长度的列表。
提示：首先编写一个函数来计算超出部分的概率分布。这可以通过动态规划高效完成。
这是什么意思呢？我在解决背包问题时没有遇到什么大问题（包括0/1背包和无限背包），但我对这个完全不知道该怎么做？
最简单的问题是先解决等级1，假设有一个属性分数是12（用上面的例子）——通过的概率就是12/20，对吧？那么等级2就是13/20，等级3就是14/20？
我这样理解对吗？我感觉我可能对游戏规则有些误解。
3 个回答
这里有个有趣的数学概念，涉及概率和多项式。比如，掷一个六面骰子可以用一个多项式来表示：
x + x^2 + x^3 + x^4 + x^5 + x^6
-------------------------------
6 ,
因为掷出1的概率是1/6（对应的项是x/6），掷出2的概率也是1/6（对应的项是x^2/6），依此类推。如果我们掷一个20面骰子，并计算超过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 + 2x + x^2)/4，然后再用(1 + 2x + x^2)/4乘以(1 + x)/2，得到(1 + 3x + 3x^2 + 1)/8，依此类推。
问题是：你可以用属性12、13和12，以及一个天赋值7，掷骰子有多少种方法。假设你已经知道第一次掷出的结果，比如是11。那么问题就变成了：用属性13和12，以及天赋值7，你还有多少种掷骰子的方法。接下来，试试第一次掷出不同的结果，比如第一次掷出14。你超出了2点，所以现在的问题是：用属性13和12，以及天赋值5，你还有多少种掷骰子的方法。再试一次，假设第一次掷出20。现在的问题是：用属性13和12，以及天赋值-1，你还有多少种掷骰子的方法（在这种情况下，显然是0种）。
一次对某个属性值为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]的测试代码。
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)