期望DP的一般思路 期望DP的一般思路
转载自___new2zy___
期望(dp)，也加概率(dp)
一般来说，期望(dp)找到正确的状态后，转移是比较容易想到的。
但一般情况下，状态一定是“可数”的
事实上，将问题直接作为(dp)的状态是最好的。
如，问“(n)人做(XX)事的期望次数”，那么不妨设计状态为(f[i])表示(i)个人做完事的期望。
转移一般是递推，通常分两种，一种是从上一个状态转移得（填表法），另一种是转移向下一个状态（刷表法）。
有时期望(dp)需以最终状态为初始状态转移，即逆推。
如f[i]表示期望还要走f[i]步到达终点。这种状态的转移是刷表法
形如(f[i]=∑p[i→j]*f[j]+w[i→j])，其中(p)表示转移的概率，(w)表示转移对答案的贡献。
一般来说，初始状态确定时可用顺推，终止状态确定时可用逆推。
大概期望(dp)的套路就是这样了吧。。。（我还是菜讲得不太好）