$f(i) :=$ マス$i$からゴールするまでにサイコロを振る回数の期待値、として降順にDPしたいが、振り出しに戻る場合の扱いを考えなくてはならない。
通常、ループを含む確率DPは左辺と右辺の両方に$f(i)$が登場する式が立式できて、$f(i) = ...$となるように整理すると遷移がわかるはずだが、この場合は紙の上で式変形するのは難しそうに見える。そこで、$f(1)$の係数も別にDPで求めることにする。つまり、$f(i) = a(i) + b(i)f(1)$と表して、$a, b$を降順で求める。
$x_i>0$なら
$$ a(i) = a(i + x_i) $$ $$ b(i) = b(i + x_i) $$$x_i = 0$なら
$$ a(i) = \frac{1}{6}(a(i+1) + ... + a(i+6)) + 1 $$ $$ b(i) = \frac{1}{6}(b(i+1) + ... + b(i+6)) $$$x_i = -1$なら
$$ a(i) = 0 $$ $$ b(i) = 1 $$これで$a(1), b(1)$が得られるので、答えは$f(1) = a(1)/(1-b(1))$と求まる。
