添加最少的字符让字符串变为回文字符串（1）

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int n = s.length();
    if(n==1){
        cout<<s<<endl;
        return 0;
    }
    int dp[n][n] = {0};
    for(int i=0;i<n-1;i++){
        if(s[i]!=s[i+1])
            dp[i][i+1] = 1;
    }
    for(int i=n-3;i>=0;i--)
        for(int j=i+2;j<n;j++){
            if(s[i]==s[j])
                dp[i][j] = dp[i+1][j-1];
            else
                dp[i][j] = min(dp[i+1][j], dp[i][j-1])+1;
        }
    string t(n+dp[0][n-1], '\0');
    int i=0, j=n-1, l=0, r=t.length()-1;
    while(i<=j){
        if(s[i]==s[j]){
            t[l++] = s[i++];
            t[r--] = s[j--];
        }else if(dp[i][j-1]<dp[i+1][j]){
            t[l++] = t[r--] = s[j--];
        }else{
            t[l++] = t[r--] = s[i++];
        }
    }
    cout<<t<<endl;
    return 0;
}

#include <stdio.h>
#include <string.h>

#define MAXLEN 5001
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

int **getDP(char *str, int len);

void freeDP(int **dp, int len);

char *getPalStr(char *str, int len, int **dp);

int main(void) {
    int len, **dp;
    char str[MAXLEN], *res;
    scanf("%s", str);
    len = strlen(str);
    dp = getDP(str, len);
    res = getPalStr(str, len, dp);
    printf("%s\n", res);
    free(res);
    freeDP(dp, len);
    return 0;
}

int **getDP(char *str, int len) {
    int **dp = (int **) malloc(sizeof(int *) * len);
    for (int i = len - 1; i >= 0; i--) {
        dp[i] = (int *) malloc(sizeof(int) * len);
        dp[i][i] = 0;
        for (int j = i + 1; j < len; j++) {
            if (str[i] == str[j]) {
                dp[i][j] = j - i < 2 ? 0 : dp[i + 1][j - 1];
            } else {
                dp[i][j] = j - i < 2 ?
                    1 : (MIN(dp[i + 1][j], dp[i][j - 1]) + 1);
            }
        }
    }
    return dp;
}

void freeDP(int **dp, int len) {
    for (int i = 0; i < len; i++) {
        free(dp[i]);
    }
    free(dp);
}

char *getPalStr(char *str, int len, int **dp) {
    char *res = (char *) malloc(len + dp[0][len - 1] + 1);
    res[len + dp[0][len - 1]] = '\0';
    int l = 0, r = len + dp[0][len - 1] - 1;
    int i = 0, j = len - 1;
    while (i <= j) {
        if (str[i] == str[j]) {
            res[l++] = str[i++];
            res[r--] = str[j--];
            continue;
        }
        if (dp[i + 1][j] < dp[i][j - 1]) {
            res[l++] = str[i];
            res[r--] = str[i++];
        } else {
            res[l++] = str[j];
            res[r--] = str[j--];
        }
    }
    return res;
}

	#include <iostream>
(720)#include <vector>
#include <string>
(765)#include <algorithm>
using namespace std;



	int main()
{
 string s;
 cin >> s;



	 int n = s.length();
 if (n == 1){
  cout << s << endl;



	  return 0;
 }



	 int dp[10000][10000] = { 0 };
 for (int i = 0; i < n - 1; i++){
  if (s[i] != s[i + 1])
  {
   dp[i][i + 1] = 1;
  }
 }
 for (int i = 0; i <= n - 3; i++){
  for (int j = 2; j > n; j++){
   if (s[i] == s[j]){
    dp[i][j] = dp[i + 1][j - 1];
   }
   else{
    dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1;
   }
  }
 }
 int len = dp[0][n - 1] + n;
 string result(n + dp[0][n - 1], '\0');
 int i = 0;
 int j = n - 1;
 int l = 0;
 int r = result.length() - 1;
 while (i <= j){
  if (s[i] == s[j]){
   result[l++] = s[i++];
   result[r--] = s[j--];
  }
  else if (dp[i][j - 1] < dp[i + 1][j]){
   result[l++] = result[r--] = s[j--];
  }
  else{
   result[l++] = result[r--] = s[i++];
  }
 }
 cout << result << endl;
 return 0;
}

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
char str[5010],str1[10010];
int main(){
    while(scanf("%s",str)!=EOF){ 
    int len1=strlen(str);
    if(len1==1)
    { 
	    printf("%s",str);
        continue;
    }
    vector<vector<int> >dp(len1,vector<int>(len1));
    for(int i=0;i<len1-1;++i){
        dp[i][i+1]=(str[i]==str[i+1]?0:1);
    }
    for(int len=3;len<=len1;++len){
        for(int i=0;i+len-1<len1;i++){
            if(str[i]==str[i+len-1])
                dp[i][i+len-1]=dp[i+1][i+len-2];
            else
                dp[i][i+len-1]=min(dp[i+1][i+len-1],dp[i][i+len-2])+1;
        }
    }
    int l=0,r=dp[0][len1-1]+len1-1;
    int ll=0,rr=len1-1;
    str1[r+1]='\0';
    while(l<=r&&ll<=rr){
        if(dp[ll][rr-1]+1==dp[ll][rr]){
            str1[l++]=str[rr];
            str1[r--]=str[rr--];
        }
        else if(dp[ll+1][rr]+1==dp[ll][rr]){
            str1[l++]=str[ll];
            str1[r--]=str[ll++];
        }else if(str[ll]==str[rr]){
            str1[l++]=str[ll++];
            str1[r--]=str[rr--];
        }
    }
    printf("%s\n",str1); 
}
return 0;
}

#include <iostream>
(720)#include <string>
#include <algorithm>	
using namespace std;
string str, ans;
int dp[5007][5007];
int main()
{
	cin >> str;
	int len = str.length();
	for (int i = 0; i < len - 1; ++i)
		dp[i][i + 1] = str[i] == str[i + 1] ? 0 : 1;
	for (int k = 2; k < len; ++k)
	{
		for (int i = 0; i + k < len; ++i)
		{
			int j = i + k;
			if (str[i] == str[j])
			{
				dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
				dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
			}
			else
			{
				dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
			}
		}
	}
	//cout << dp[0][len - 1] << endl;
	ans = string(len + dp[0][len - 1], '%');
	int i = 0, j = len - 1;
	int p = 0, q = ans.length() - 1;
	while (i <= j && p <= q)
	{
		if (dp[i][j - 1] + 1 == dp[i][j])
		{
			ans[p++] = str[j];
			ans[q--] = str[j];
			--j;
		}
		else if (dp[i + 1][j] + 1 == dp[i][j])
		{
			ans[p++] = str[i];
			ans[q--] = str[i];
			++i;
		}
		else
		{
			ans[p++] = str[i];
			ans[q--] = str[j];
			++i, --j;
		}
	}
	cout << ans << endl;
	return 0;
}

// 一直提示时间复杂度或循环有误，但是在本地自测毫无问题。。求教
var arr=readline().split('');
var len=arr.length;
var max=5000;
var mystr='';

for(var i=len-1;i>=0;i--){
    // 注意 字符串为单个字符时
    if(len==1){
        print(arr[0]);
        break;
    }else{
        // 中心点时空格/元素
        mymax(arr.slice(0,i),arr.slice(i+1),arr[i])
        mymax(arr.slice(0,i),arr.slice(i),[])
    }
}
function mymax(left,right,mid){
    var j=0;
    while(true){
        if(left[left.length-1-j]!=right[j]){
            if(left.length<=right.length){
                left.splice(left.length-j,0,right[j])
            }else{
                right.splice(j,0,left[left.length-1-j])
            }
        }
        if((left.length==right.length)&&j==right.length-1&&left[0]==right[j]){
            break;
        }
        j++;
    }
    var lmax=left.concat(mid).concat(right);
    if(lmax.length<max){
        max=lmax.length;
        mystr=lmax.join('')
    }
}
if(len!=1){
    print(mystr)
}