回文串与动态规划中的最长公共子序列

题目：给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

解题思想：此处利用求原字符串和其反串的最大公共子序列（不是子串，因为可以不连续）的长度（使用动态规划很容易求得），然后用原字符串的长度减去这个最大公共子串的长度就得到了最小编辑长度。

1、回文串：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

2、动态规划：动态规划算法通常用于求解具有某种最优性质的问题。

（1）最大公共子序列：（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。

应用在可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。

注：最长公共子序列与最长公共子串不同，最长公共子串为给定串中任意个连续的字符组成的子序列称为该串的子串。

下面来计算一个字符串中最长公共子序列的长度。

用到的公式为：

A=a1a2……aN，表示A是由a1a2……aN这N个字符组成，Len(A)=N
　  B=b1b2……bM，表示B是由b1b2……bM这M个字符组成，Len(B)=M

第一步矩阵MaxLen[A.length+1][B.length+1]初始化：行为A字符串GAATTCAGTTA，列为B字符串GGATCGA如下图：

第二步计算距离设行为k列为k2，当A字符串k-1与B字符串k2-1的字符相等时，矩阵MaxLen[k][k2] = MaxLen[k-1][k2-1] + 1（即左上角数+1）;否则MaxLen[k][k2] = Math.max(MaxLen[k-1][k2], MaxLen[k][k2-1])（当前位置的左侧数与上方数比较，取二者中大的）

最后全部计算完成后，其矩阵MaxLen[A.length+1][B.length+1]数就是最长公共子序列中含有的字符数。

所以本题删除个数为A.length-MaxLen[A.length+1][B.length+1]。

3、java代码如下

public class Huiwen {

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("输入字符串");
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){//检测键盘是否还有输入
String strArray = scan.next();
System.out.println(strArray);
StringBuffer sb = new StringBuffer(strArray);
String strArray2 = sb.reverse().toString();//将输入字符串翻转，如abcd变为dcba
char[] cha = strArray.toCharArray();
char[] cha2 = strArray2.toCharArray();//string变为char型数组

int[][] MaxLen = new int[cha.length + 1][cha2.length + 1];

for (int k = 0; k < MaxLen.length; k++) {//行初始化
MaxLen[k][0] = 0;
}
for (int k = 0; k < MaxLen[0].length ; k++) {//列初始化
MaxLen[0][k] = 0;
}
//动态规划
for (int k = 1; k < MaxLen.length; k++) {
for (int k2 = 1; k2 < MaxLen.length; k2++) {
if (cha[k-1] == cha2[k2-1]) {
MaxLen[k][k2] = MaxLen[k-1][k2-1] + 1;
}
else{
MaxLen[k][k2] = Math.max(MaxLen[k-1][k2], MaxLen[k][k2-1]);
}
}
}
for (int m = 0; m < MaxLen.length; m++) {
for (int k = 0; k < MaxLen.length; k++) {
System.out.print(MaxLen[m][k] + " ");
}
System.out.println();
}
int deletNum = cha.length - MaxLen[cha.length][cha2.length];//输出删除个数
System.out.println(deletNum);
}
}

}

输出结果：

参考：http://www.cnblogs.com/grenet/archive/2010/06/03/1750454.html

https://blog.****.net/hrn1216/article/details/51534607