\(dp[l][r][c]\) を、最初はすべて文字 \(c\) で塗られていると仮定したときに区間 \([l, r)\) を塗るための最小手数とします。

最初は何も塗られていないので、53文字目の文字 $ などを導入して代用します。

DP

次の DP で解くことができますが、計算量は \(\sigma = 53\) として \(O(N^3 \sigma)\) となっているため、実行時間制限に間に合いません。

• \(S_l=c\) のとき、\(\mathrm{chmin}(dp[l][r][c], dp[l+1][r][c])\) とする
• \(S_l \ne c\) のとき、\(\mathrm{chmin}(dp[l][r][c], \min_{l+1\le k \le r} (dp[l+1][k][S_l] + dp[k][r][c] )+ 1)\)
• \(r\) についても同様

このDPでは、一番左端が違う色で塗られている場合、それをどこまで塗るかを全部調べています。

高速化

考えると、

\[\min_{l+1\le k \le r} (dp[l+1][k][S_l] + dp[k][r][c] )+ 1)\]

における \(k\) は \(S_{k-1} = S_l\) となるようなもののみとして良いということが言えます。

実際に、もし右端 \(S_{k-1}\) が \(S_l\) と異なる色であったら、 結局 \(S_{k-1}\) は一手かけてまた塗ることになります。そうすると、代わりに \([l,k-1)\) を塗ることにしても損をしません。よって、 \([l,k)\) を塗ることは考えなくてよいです。

\(r\) に関しても同様です。

こうすると、\(dp[l][r]\) では遷移の合計の計算量が \(O(N)\) となり、合計 \(O(N^3)\) で解けます。