寻找可能利润的算法

Question

我正在寻找一种算法(除了朴素的蛮力解决方案没有运气)能够有效地(最好是 O(n^2))执行以下操作:

假设我在玩一个游戏，在这个游戏中我必须回答 n 个问题(每个问题来自不同的类别)。对于每个类别“i”i=1,...,n，我计算了给出正确答案的概率 p_i。

对于连续的 k 个正确答案，我得到 k^4 分。预期平均利润是多少？

我将在以下示例中阐明预期利润的含义:

在 n=3 和 p_1=0.2,p_2=0.3,p_3=0.4 的情况下

预期利润为

EP= (0.2* 0.3* 0.4 )3^4+(我的 3 个答案都正确)

• (0.2* 0.3* 0.6 )2^4+ (0.8* 0.3* 0.4 )2^4+ (0.2* 0.7* 0.4 )2+ (2 个答案正确)

• 0.2* 0.7* 0.6 ) + (0.8* 0.3* 0.6 )+ (0.8*0.7* 0.4 ) (1 个答案正确)

  很明显，对于每个可能的结果，我都在计算概率并将其与获得的分数相乘。然后计算所有这些的总和。

有什么想法吗？我只对总和本身感兴趣。

谢谢!

Answer 1

让A[t]是t之后的预期利润鉴于t = 0的问题, t = n ，或 t '的问题回答错了。然后你可以计算

A[0] = 0

A[t] = sum(i = 0..t-1) (得到问题的概率 i .. t-2 正确和 t-1 错误) * (( t-i-1 )⁴ + A[ i]) 当0 < t < n .

A[n]计算类似于上面的一般情况，除了你还应该在 i 之后添加一个术语来表示所有问题。回答正确。