大概题意就是求最少添加多少个字符可以把长度为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; }
