构造回文

https://www.nowcoder.com/test/question/28c1dc06bc9b4afd957b01acdf046e69?pid=1725829&tid=14425231

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

输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子1:
abcda
google

输出例子1:
2
2

分析：

回文翻转后和原来是一样的，这样就是求两个字符串中的最长公共子序列了，不要求子串连续。
比如：abcda 翻转后 -> adcba，明显只有 aba 是最长的回文，而且是最长的公共子序列。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			String s1 = in.sval;
			StringBuffer tmp = new StringBuffer(s1);
			String s2 = tmp.reverse().toString();
			out.println(s1.length() - LCS(s1, s2));
		}
		out.flush();
	}

	static int LCS(String s1, String s2) {
		int s1Length = s1.length(), s2Length = s2.length();
		int[][] dp = new int[s1Length + 1][s2Length + 1];

		for (int i = 1; i <= s1Length; i++) {
			for (int j = 1; j <= s2Length; j++) {
				if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[s1Length][s2Length];
	}
}