P4170
区间dp。
转移方程见题解（doge）
#include<bits/stdc++.h>
using namespace std;
int m[310],dp[310][310],ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
string c;
cin>>c;
int n=c.size();
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int s=1;s<n;s++){
for(int l=1;l+s<=n;l++){
dp[l][l+s]=114514;
if(c[l-1]==c[l+s-1])dp[l][l+s]=min(dp[l+1][l+s],dp[l][l+s-1]);
else for(int i=1;i<=s;i++)dp[l][l+s]=min(dp[l][l+s],dp[l][l+i-1]+dp[l+i][l+s]);
}
}
cout<<dp[1][n];
}