我正在寻找一种算法（除了天真的蛮力解决方案没有运气），它有效地（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个答案正确）
显然，对于每个可能的结果，我都在计算概率并将其乘以获得的分数。然后从所有这些中扣除总和。
有任何想法吗？我只对总和本身感兴趣。
谢谢！