成功確率 \(P\) の試行を成功するまで繰り返す際の試行回数の期待値が \(1/P\) であることから、 \[ \begin{aligned} \mathrm{dp} _ i: =&「マス\ i\ からマス\ N\ までの回数の期待値」\\ =&「\ 0\ 以外の目が出るまでの回数の期待値」+「\ \mathrm{dp} _ {i+1}, \ldots, \mathrm{dp} _ {i+A_i}\ の平均値」\\ =&\ \left( 1 \middle/ \frac{A_i}{A_i+1} \right) + \frac{S}{A_i} \quad \left(S := \sum _ {j=1}^{A_i}\mathrm{dp} _ {i+j}\right) \\ =&\ \frac{A_i+1+S}{A_i} \end{aligned} \] となるので、これを \(i\) の大きい方から順に累積和などを用いて計算すればよい。