回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。
比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。
注：此问题区分大小写
一个字符串(0<strlen<=1000)
有且只有一个整数，即最少插入字符数
Ab3bd
2
简单dp题，编辑距离即可
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 using namespace std; 6 int dp[3005][3005]; 7 int main() { 8 string a; 9 string b; 10 cin>>a; 11 b=a; 12 reverse(b.begin(),b.end());//string反转函数，将字符串左右颠倒 13 int lena=a.size(); 14 for(int i=1;i<=lena;i++){ 15 for(int j=1;j<=lena;j++){ 16 if(a[i-1]==b[j-1]){ 17 dp[i][j]=dp[i-1][j-1]+1; 18 }else{ 19 dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 20 } 21 } 22 } 23 cout<<lena-dp[lena][lena]<<endl; 24 return 0; 25 }
原文：https://www.cnblogs.com/FedLx/p/11525668.html