期待値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)