题目链接: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;
}