TopCoder SRM 381 Div1 Easy TheDiceGame

問題

1〜6の数字をもつダイスがある。
これを振ると、出た目の数だけキャンディが貰える。
n個のキャンディを貰えるまでダイスを振り続けるとき、ダイスを振る回数の期待値を求めよ。

制約条件

n≦1000000

方針

DP.
dp[i]をi個のキャンディを貰えるまでに振るダイスの期待値とすると、
線形性から、
dp[i]=Σ[j=1,6](dp[i-j]+1)/6が成り立つ。

ソースコード

double dp[1000001];
class TheDiceGame {
  public:
  double expectedThrows(int n) {
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
      rep(j,6)dp[i]+=(dp[max(0,i-j-1)]+1)/6;
    }
    return dp[n];
  }
};