http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28415#problem/D
题目大意：给一个长为n的字符串，问最少插入几个字符成回文串
解题思路：总长-最长公共（原来的和其倒过来的串）子序列（LCS）
知识详解——LCS:给出两个子序列A,B，求长度最大的公共子序列（如152687和2356984——>568或268）；不妨设d(i,j)为A,B的LCS, 则最有子结构为::A[i]=B[j]时，d(i,j)=d(i-1,j-1)+1;否则，d(i,j)=max{d(i-1,j),d(i,j-1)};复杂度为O（m*n),也可用滚动数组法优化。
View Code
注意： 上面的代码虽然实现了求解，但是 由于开了一个c[2005][2005]的数组所以不幸“Memory Limit Exceeded”，通过观察不难发 |
View Code
