题解

#include<bits/stdc++.h>
using namespace std;
const int N=666;
string s;
int m,a[N],dp[N][N],sum[N];
int main(){
	cin >> s;
    int n=s.size();
    s="!"+s;
	memset(dp,0x3f,sizeof dp);
	for(int i=1; i <= n; i ++){
		dp[i][i] = 1;
	}
	for(int len = 2;len <= n; len++){
		for(int l = 1; l + len - 1 <= n; l++){
			int r = l + len - 1;
            if(s[l]==s[r]){
                if(len==2) dp[l][r]=1;
                else dp[l][r]=min(dp[l][r],dp[l+1][r-1]);
            }
			for(int k = l; k <= r-1; k ++){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
			}
		}
	}
	cout << dp[1][n];
    return 0;
}[:思考][:ACGO_大佬]