期待値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)
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]