期待値DP

• f(x)をxの状態からNになるまでの操作の回数の期待値とする。f(N) = 0。f(1)を求めたい
• f(x)が与えられたとしてf(x-1)を求める
  • x-1の状態から1ステップ後を考える
  • P の確率でx-1にとどまる
  • (1 - P)の確率でxになる
  • $f(x-1)-1=Pf(x-1)+(1-P)f(x)$
  • $(1-P)f(x-1)=(1-P)f(x)+1$
  • $f(x-1)=\left((1-P)f(x)+1\right)/(1-P)$

ABC194D