[数据结构与算法]2021.7.10

第二天，居然迟到了，闹钟响了之后不该再睡的。
今天的就是把昨天剩下的动态规划。
1、概率dp
这种一般题目里面会有概率或期望问题。
一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到高斯消元来优化。


2、dp求期望

3、单调队列、栈优化dp
特征总结：当前状态的所有值可以从上一个状态的某个连续的段的值得到，要对这个连续的段进行 RMQ 操作，相邻状态的段的左右区间满足非降的关系。

晚上补了一场之前的CF，很巧C题就是个概率DP