RT,一般我们设置的状态是
f[i]表示从
i到
k的期望,然后发现复杂度太大,于是
这篇题解给了一个解决方案;但是这篇题解没有改变
f的状态,而最高赞题解认为
f[i]表示从
i到
i−1的期望,如果是这样的话,递推方程还是那个吗?
假设从
i+1到
i的各个样本分别是
(x1,p1),(x2,p2),...(
x表示操作次数,
p表示概率),那么有
f[i+1]=∑xipi;同理设
i到
i−1的各个样本分别是
(y1,q1),(y2,q2),...,那么有
f[i]=∑yiqi;递推公式则有
f[i]=ni×1+nn−i×(i∑j∑(1+xi+yj)pipj)=ni+nn−i(f[i+1]Pi+f[i]Pi+1+PiPi+1),其中
Pi表示从
i到
i−1的概率
请问一下上述推导有什么问题吗(我概率期望都是自学的qaq可能学假了,请多指教)