parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ dp[i][j]:=左は文字iまで、右側はjまで見たときの偶数長(長さ0以上)の回分の個数の数(ただし1<=i<=j<=N) たとえば、文字列sが以下のような形の場合(1-indexed) abcxycba abc...ba dp[3][7] = 2^2 = 4 1<=j-i<=nを nから順に確定していけばいい。つまり dp[i][j] = dp[i-1][j] + dp[i][j+1] - dp[i-1][j+1] + (s[i]==s[j]?dp[i-1][j+1]:0) = dp[i-1][j] + dp[i][j+1] - (s[i]==s[j]?0:dp[i-1][j+1]) 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F02%2F10%2F135714" title="SRM 708 DIV2 Hard: PalindromicSubseq2 - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/parukii/20170210/20170210135639.jpg Hatena Blog https://hatena.blog 2017-02-10 13:57:14 rich https://par.hateblo.jp/entry/2017/02/10/135714 1.0 100%