• 对于期望 DP，我们一般采用逆序来定义状态，即考虑从当前状态到达终点的期望代价。
  • 根据期望的线性性质计算出数学期望表达式

注意点

  • E[X^2] \neq (E[X])^2$$ -> 正确的代入姿势：展开全平方公式

收集邮票

  • 核心模型:期望dp
  • 思维误区 (Bug):展开完全平方式，x->f(x) x^2->g(x)注意一一映射关系
  • 理解递推公式:
    • 当前状态的期望 = ∑[转移到下一个状态的概率×(下一个状态的期望+本次转移的代价)]\sum [ \text{转移到下一个状态的概率} \times (\text{下一个状态的期望} + \text{本次转移的代价}) ]
    • 一维初始方程：$$E(i) = P \cdot (E(i+1) + 1) + (1-P) \cdot (E(i) + 1)$$

    • g(x)=P⋅(g(x+1)+2f(x+1)+1)⏟抽到新票的贡献+(1−P)⋅(g(x)+2f(x)+1)⏟抽到旧票的贡献g(x) = P \cdot \underbrace{(g(x+1) + 2f(x+1) + 1)}_{\text{抽到新票的贡献}} + (1-P) \cdot \underbrace{(g(x) + 2f(x) + 1)}_{\text{抽到旧票的贡献}}

  • 碎碎念：这种题最阴了，考数学还伪装成算法…
  • 关键代码:
1