很明显的一道区间dp
我们设\(dp_{i,j}\)表示清空\(i\)到\(j\)之间所有字母所需的最小操作次数
紧接着任取一个\(k\)满足\(k\in (i,j]\)
来分情况讨论：
\[ f_{i,j}= \min^j_{k=i+1} \left\{ \begin{aligned} a_i=a_k \Rightarrow f_{i+1,k-1}+f_{k,j} \\ f_{i+1,k-1}+f_{k+1,j}+1 \end{aligned} \right. \]初始化只需要使\(dp_{i,i}=1\)，其他位置都是一个极大值即可
需要注意一下，因为我们的循环是从\(i+1\)开始的，但是\(k=i+1\)时，数组访问的\(f_{i+1,k-1}\)是一个没有实际意义的（因为这个时候\(i+1>k-1\)，与事先定义的\(f_{i,j}\)不符），所以这里应该是\(0\)，赋初始值的时候需要注意一下
接着即可写出代码：
#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int dp[550][550];
int main()
{
cin>>n>>s;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
dp[i][j]=1e9+10;
}
dp[i][i]=1;
}
for(int l=2;l<=n;l++)
{
for(int i=1;i+l-1<=n;i++)
{
int j=i+l-1;
for(int k=i+1;k<=j;k++)
{
dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]+(s[i-1]!=s[k-1]));
}
}
}
cout<<dp[1][n];
return 0;
}