一、前言
只是一些自己的理解，并不知正确与否。
首先期望 \(dp\) 分为 伪期望 \(dp\) 和真期望 \(dp.\)
二、伪期望 \(dp\)
对于伪期望 \(dp\) 来说，其在定义状态之后，一般可以认为状态之间的转移是 线性 的，即每一个 \(dp\) 状态转移到何处具有 唯一对应性，只不过具体的实现上经过了概率论的包装。
三、真期望 \(dp\)
对于真期望 \(dp\) 来说，一个状态往往可以转移到 \(n\) 个状态去，并不具有 唯一对应性。
3.1 树形 \(dp\)
因此我将真期望 \(dp\) 理解为了具象的 树形 \(dp\) 。
不难发现两者的转移具有相似性：若将 每一个状态具象化为树上的一个节点 \(i\)，那么这个状态所转移到的每一个状态分别对应 \(siz_i\) 个子结点， 我们知道树形 \(dp\) 的常见套路是在 \(dfs\) 回溯的过程中统计答案，这样做的本质是 倒序地枚举树的每一层节点，只不过在期望 \(dp\) 中我们的层数对应的是往往题目中出现的每一个阶段，因此我们可以用 看似是倒序线性 \(dp\) 的方法真正实现了对一颗状态树的枚举，这也是一般的真期望 \(dp\) 通常都可以用记忆化搜索来解决的原因。对于节点 \(i\) ，通过树形 \(dp\) 得到了每一个转移对象 \(j\) 的贡献 \(dp_j\)，就可以采用期望的定义来进行计算 \(dp_i\) 了。最终和树形 \(dp\) 一样，根节点 \(root\) 的 \(dp\) 值就是答案。因此我认为将 P4316 绿豆蛙的归宿 作为真期望 \(dp\) 的模板题目是十分合适的，因为这道题目展现了期望 \(dp\) 的本质和一般性解法。
3.2 考虑地深一些
那我就是任性，偏偏要正序 \(dp\) 怎么办?
考虑到部分树形 \(dp\) 也可以按 \(dfs\) 序来正序转移。考虑当树形 \(dp\) 的答案统计的实质为 某一条树上最满足某种性质的链 时，我们完全可以正序枚举统计答案到每一个根节点再求出最终解。我们可以通过这种思路来正序枚举解期望 \(dp.\)
显然期望 \(dp\) 的每个期望正好对应着状态树上每一条链的期望。 由 期望的线性性质 可以得到，最终状态的期望 \(E\) 本质上是 上文所说状态树中所有叶节点的期望之和。 因此我们需要算出每一个最终状态的期望值。由公式 \(E=P\times val\)，我们还需要维护 根节点到达节点 \(i\) 的概率 \(p_i\) ，与 \(val_i\) 相乘即可算出期望 \(E_i\) ，那么加和就能算出最终答案了。
四、推导过后的思考
推导这些东西的来源是做 SCOI2008 奖励关 时对期望 \(dp\) 产生了各种各样的疑问，遂开始思考期望 \(dp\) 的本质，便得到上方的拙见，个人以为大概可以解释期望 \(dp\) 一些概念上的问题了。不过期望 \(dp\) 的题目刷了二十余道才生出这些见解，直接反映出我刷题质量的堪忧，今后还是一定要多思考啊。
标签：状态,期望,树形,思考,正序,节点,dp From： https://www.cnblogs.com/Rock-N-Roll/p/18129972