数据范围 $l\le 1000$，但我 $O(l^3)$ 都给卡过了。

测评记录

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string a;
int dp[1010][1010];
int main()
{
	cin>>a;
	int l=a.size();
	a=' '+a;
	memset(dp,1,sizeof(dp));
	for(int i=1;i<=l;i++)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=0;
		}
	}
//	for(int i=1;i<=l;i++)
//	{
//		for(int j=1;j<=l;j++)
//		{
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	for(int k=1;k<=l;k++)
	{
		for(int i=1;i<=l;i++)
		{
			for(int j=i;j<=l;j++)
			{
				if(a[i]==a[j])dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
				else dp[i][j]=min(dp[i][j],min(dp[i+1][j]+1,dp[i][j-1]+1));
				//cout<<dp[i][j]<<" ";
			}
			//cout<<endl;
		}
	}
	cout<<dp[1][l];
	return 0;
}