poj1159

题意：求对字符串最少添加几个字符可变为回文串。

分析：简单做法是直接对它和它的逆序串求最长公共子序列长度len。n-len即为所求。(n为原串长度)

这样做的原因如下：

要求最少添加几个字符，我们可以先从原串中找到一个最长回文串，然后对于原串中不属于这个回文串的字符，在它关于回文串中心的对称位置添加一个相同字符即可。那么需要添加的字符数量即为n-最长回文串长度。

最长回文串可以看作是原串中前面和后面字符的一种匹配（每个后面的字符在前面找到一个符合位置要求的与它相同的字符）。这种的回文匹配和原串与逆序串的公共子序列是一一对应的（一个回文匹配对应一个公共子序列，反之亦然），而且两者所涉及到的原串中的字符数量是相等的，也就是最长公共子序列对应最长回文串。原因陈述完毕。

还有另一个动态规划的方法。

f[i][j]表示从i到j这段子串若变为回文串最少添加的字符数。

if (st[i] == st[j])
                f[i][j] = f[i + 1][j - 1];
else
                f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
usingnamespace std;

#define maxn 5005

char st[maxn];
int n;
short f[maxn][maxn];

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d", &n);
    scanf("%s", st);
    for (int i = n -1; i >=0; i--)
    {
        f[i][i] =0;
        for (int j = i +1; j < n; j++)
            if (st[i] == st[j])
                f[i][j] = f[i +1][j -1];
            else
                f[i][j] = min(f[i +1][j], f[i][j -1]) +1;
    }
    printf("%d\n", f[0][n -1]);
    return0;
}