考えたこと
長さ5000以下なのでO(|S|^2)までいけそう
dp[i][j] = (i番目までの文字列で長さjの回文がつくれる確率）を考える
区間[i+1, j)が回文かどうか前計算で求めておくのをとりあえず実装してみる
この実装をしてたら幅が小さい方から埋めていくDPを最初からすればいいのではと思う
dp[l][r] = (区間[l, r]が回文になる確率) として幅が小さい区間から順に埋めていくと考えた
試してみたらよさそうで実装したら通った
解法
dp[l][r] = (区間[l, r]が回文になる確率) として幅が小さい区間から順に埋めていく。
dp[l][r]は
- S[l]、S[r]が両方とも'?'でなく一致していれば dp[l][r] = dp[l+1][r-1]
- S[l]、S[r]が両方とも'?'でなく一致していなければ dp[l][r] = 0
- S[l]、S[r]のどちらかが'?'であれば dp[l][r] = dp[l+1][r-1]/26
となる。
