[ACM_动态规划] Palindrome

<a href="http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28415#problem/D">http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28415#problem/D</a>

题目大意：给一个长为n的字符串，问最少插入几个字符成回文串

解题思路：总长-最长公共（原来的和其倒过来的串）子序列（LCS） 

知识详解——LCS:给出两个子序列A,B，求长度最大的公共子序列（如152687和2356984——&gt;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

本文转自beautifulzzzz博客园博客，原文链接：http://www.cnblogs.com/zjutlitao/p/3245558.html，如需转载请自行联系原作者