一句话理解
期望 DP：f[s] 表示从 s 出发的期望。
为什么要学
常从目标倒推。
讲解
f[终]=0，f[s]=1 + ∑p f[nxt] 这类。有环用高斯。
例子
期望步数。自己转移到自己要移项。
常见错误
- 正推期望在吸收态搞错。
- 自环没移项。
第 360 课
期望 DP
🟣 竞赛 约 14 分钟
练习 做完再看下一课
期望步数常列出 f[s]=1+转移期望 再解方程。
进度保存在本机浏览器里。
左右方向键也可翻课
第 360 课
期望 DP：f[s] 表示从 s 出发的期望。
常从目标倒推。
f[终]=0，f[s]=1 + ∑p f[nxt] 这类。有环用高斯。
期望步数。自己转移到自己要移项。
期望步数常列出 f[s]=1+转移期望 再解方程。
左右方向键也可翻课