期待値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 = P f(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