大概题意就是求最少添加多少个字符可以把长度为N的字符串编程回文串。
则需要最少需要补充的字母数 = 原序列S的长度 — S和S'的最长公共子串长度
S'为原串的逆串。
关于求最长公共子串， 用到的是动态规划
伪代码如下
if( i ==0 || j == 0 ) {
MaxLen(i, j) = 0 //两个空串的最长公共子序列长度当然是0
}
else if( s1[i] == s2[j] )
MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1;
else {
MaxLen(i, j) = Max( MaxLen(i, j-1), MaxLen(i-1, j));
}
具体可参考算法导论第三版222页
//2013-05-30-19.58
//poj 1159
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 5005;
short dp[maxn][maxn];
char s1[maxn], s2[maxn];
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
getchar();
for (int i = 1; i <= n; i++)
{
scanf("%c", &s1[i]);
s2[n-i+1] = s1[i];
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (s1[i] == s2[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
printf("%d\n", n-dp[n][n]);
}
return 0;
}
