$dp[l][r]$ を区間 $[l,r)$ を塗るための最小手数とします。 $l \geq r$ ならば $0$ とし、 $l+1=r$ ならば $1$ とします。入力の文字列の $i$ 文字目を $s[i]$ とします。
区間を塗るとき、その区間の両端の色が異なると無駄に広く塗っているので一色で塗る区間の両端は同じ色として構いません。塗る区間同士の関係を考えると、どの $2$ つをとっても内包もしくは重なっていない関係が最適です。内包する区間については離れた同じ色同士を先に塗るという感覚です。

DP区間を併合することを考えます。左側の区間と右側の区間が同じ色なら先にその \(2\) つを塗ってしまえばいいことを留意すると漸化式は以下のようになります。

\(dp[l][r] = \min(dp[l][k+1]+dp[k+1][r]) - \left( s[l]==s[r-1] \right) \left( l \leq k \leq r-1 \right)\)

これは区間DPの形なので \(O(N^3)\) で解くことができます。