概率期望

$p[j]$p[j]表示在$i$i状态时变成$j$j状态的概率，$p[j]+p[k]+p[l]=1$p[j]+p[k]+p[l]=1。

• 如果图中的$dp[i]$dp[i]表示到达完成态的概率。
  $dp[i]=p[j]\cdot dp[j]+p[k]\cdot dp[k]+p[l]\cdot dp[l]$dp[i]=p[j]⋅dp[j]+p[k]⋅dp[k]+p[l]⋅dp[l]
• 如果图中的$dp[i]$dp[i]表示到达完成态的期望步数。
  $dp[i]=p[j]\cdot (dp[j]+1)+p[k]\cdot (dp[k]+1)+p[l]\cdot (dp[l]+1)\quad$dp[i]=p[j]⋅(dp[j]+1)+p[k]⋅(dp[k]+1)+p[l]⋅(dp[l]+1)(根据题目情况看括号里面加什么)
• 一般期望$dp[i]$dp[i]表示的是还要$i$i步达到某种状态的期望。如果表示成已经走了$i$i步，那么步数有可能是无穷的。
• $E(X)=\sum_{i=1}^{n}E(x_i)$E(X)=∑i=1n​E(xi​)