2019/4/5-4/6日训练日记 概率期望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[]表示转移对答案的贡献。一般来说，初始状态确定时可用顺推，终止状态确定时可用逆推。

莫比乌斯也是看了两天了，不确定到时如果真出到自己能不能推出来，明天再看半天，之后再往前补题

清明时间太短，专题太多，慢慢来吧，受够了浮躁的心态了，慢一点也要掌握啊，别着急啊