🔍 解题思路

s为给定的字符串，e为s的逆序字符串。 最少需要补充的字母数 = 原序列s的长度 — s和e的最长公共子串长度。 原因仔细想想应该可以想出来。 这道题就变成求s和e的最长公共子串长度。也就是LCS问题。 在这里要注意定义二维数组空间会超限的，由于在LCS问题中都是相邻两个数进行比较，所以可以用滚动数组来优化空间

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[2][5005];//用滚动数组防止空间溢出
char s[5005],e[5005];//e为s的逆序数组
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",s);
	for(int i=0;i<n;i++)
	{	
		e[i]=s[n-1-i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
			if(s[i-1]==e[j-1])//由于数组下标是从0开始，所以用s[i-1]和e[j-1]来判断
			dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j-1]+1);
		}
	}
	int ans=n-dp[n%2][n];
	printf("%d",ans);
	return 0;
}