题目链接: https://syzoj.com/problem/41#submit_code
内存限制：128 MiB时间限制：1000 ms
题目描述
回文串就是类似aba, bcdcb,AAA这样的字符串。即将它反转过来，与原串相等。
另外这样的字符串，例如ab，我们可以发现，在最后补充一个a也能使它变成一个回文串 aba，或者在他的最前面插入一个b，能使它变成一个回文串bab
现在输入一个字符串（它很可能不是回文串），那么问最少给它插入多少个字符，能使它变成一个回文串?
输入格式
一行，一个字符串
字符串可能出现类似%、*等字符，保证均为可见字符。
输出格式
一个数字，需要添加的最少字符数
如果不需要添加字符，输出0
样例输入
ab
样例输出
1
数据范围与提示
2 <= 字符串长度 <= 200
保证输入的字符串中间不会出现空格
提示
把输入的字符串反转过来，与原串求LCS(最长公共子序列)，然后......
解题思路
求最长公共子序列。
#include <bits/stdc++.h>
using namespace std;
int dp[205][205];
char str[205];
int main() {
int len;
scanf("%s", str);
len = strlen(str);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++) {
if (str[i - 1] != str[len - j])
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
else dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
printf("%d\n", len - dp[len][len]);
return 0;
}
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/22198239/viewspace-2868745/ ，如需转载，请注明出处，否则将追究法律责任。
