先要搞明白：最长公共子串和最长公共子序列的区别。
最长公共子串（Longest Common Substirng）：连续
最长公共子序列（Longest Common Subsequence，LCS）：不必连续
题目：给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。
思路是：反序这个字符串，求这个新串和原串的最大子序列。abcda--->adcba 最大子序列是aca，再相减就是最少的字符删除个数。所以问题变成了求两个字符串的最长子序列。
那么怎么求两个字符串的最长子序列呢？既然是用动态规划，最重要的是确定状态和状态转移方程。
状态：当str1的下标为m，str2的下标是n的时候（不考虑后面的），此时的最长子序列长度L。
转移方程：1，如果str1(m)==str2(n)，那么L(m,n)=L(m-1,n-1)+1。2，如果str1(m)!=str2(n)，那么L(m,n)=max(L(m-1,n),L(m,n-1))。
解释一下，假如m和n相等，那么这个时候最长子序列无疑是前一个L(m-1,n-1)加上1，因为这两个字符串这个地方的字符都可以加入到最长子序列里面去。如果不相等，那么要么舍弃新来的来自str1的那个字符m号，要么舍弃str2的n号字符（最长子序列每个位置上当然都是唯一确定的一个字符），舍弃之后呢，就从
L(m-1,n),L(m,n-1)当中挑一个好的（能更长的）为当前状态的最长子序列。
代码：
public class Main { public static void main(String[] args){ Solution s = new Solution(); Scanner sc = new Scanner(System.in); while(sc.hasNextLine()) { System.out.println( s.getResult(sc.nextLine()) ); } sc.close(); }} class Solution { public int getResult(String s) { StringBuilder s1 = new StringBuilder(s); StringBuilder s2 = new StringBuilder(s).reverse(); return s.length() - LCS(s1, s2); } public int LCS(StringBuilder s1, StringBuilder s2) { int m = s1.length(); int n = s2.length(); int[][] mutrix = new int[m + 1][n + 1]; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(s1.charAt(i - 1) == s2.charAt(j - 1)) mutrix[i][j] = mutrix[i - 1][j - 1] + 1; else mutrix[i][j] = Math.max(mutrix[i - 1][j], mutrix[i][j - 1]); } } return mutrix[m][n]; }}