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

输入描述:

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

输出描述:

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

输入例子: abcda google

输出例子: 2 2

解题思路: 其实这是最长公共子序列的变种，先求出原字符串与反转串的最长公共子序列的长度，之后用原串长度减去即可。

Java代码如下：

import java.util.Scanner;
import java.lang.Math;

public class Main {
    static int[][] dp = new int[1010][1010];

    public static int GetMax(String str){
        StringBuffer buf = new StringBuffer();
        String reverse = buf.append(str).reverse().toString();
        int len = str.length();
        for ( int i = 1 ; i <= len ; i++){
            for ( int j = 1 ; j <= len ; j++){
                if ( str.charAt(i-1) == reverse.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[len][len];
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str;
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            str = in.next();
            System.out.println(str.length() - GetMax(str));
        }
        in.close();
    }

}