区间dp。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 55 #define inf 2000000000 using namespace std; int n,dp[maxn][maxn]; char s[maxn]; int main() { scanf("%s",s);n=strlen(s); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if (i==j) dp[i][j]=1; else if (i<j) dp[i][j]=inf; else dp[i][j]=0; } for (int l=2;l<=n;l++) for (int i=1;i<=n-l+1;i++) { int left=i,right=i+l-1; for (int k=left;k<=right-1;k++) dp[left][right]=min(dp[left][right],dp[left][k]+dp[k+1][right]-(s[left-1]==s[right-1])); } printf("%d ",dp[1][n]); return 0; }