}

#Python版 
#思路：最长会文字序列：==  Str与reverse_Str的最长公共字序列
#注意：碰到了楼上Python解法同样的问题，没把循环过程放到name中，一直说是过90% 
#然后超时，放进去就好了。猜一下：是不是给了程序入口能加快解析  # -*- coding:utf-8 -*-
import sys


def maxlcp(strs):
    if strs==None or len(strs)==0:
        return 0
    lens = len(strs)
    dp =[0] *lens
    dp[0] = 1 if strs[0] == strs[lens-1] else 0
    for i in range(lens):
        pre = dp[0]
        dp[0] = max(dp[0],1 if strs[i] == strs[lens-1] else 0)
        for j in range(1,lens):
            cur = dp[j]
            dp[j] = max(dp[j],dp[j-1])
            if strs[i] == strs[lens-1-j]:
                dp[j] = max(dp[j],pre+1)
            pre = cur

    return dp[lens-1]


if __name__ == '__main__':
    while True:
        line = sys.stdin.readline().strip()
        lens = len(line)
        if not line:
            break
        maxLcp = maxlcp(line)
        # print lens
        # print maxLcp
        print lens - maxLcp

include<iostream>
#include<string>

using namespace std;
const int MAX_LENGTH = 1002;
int dynamic[MAX_LENGTH][MAX_LENGTH];

int min_palindrome(string s)
{
  if(s.length() <= 1)
    return 0;
  for(int i=0; i<s.length(); ++i)
  {
    dynamic[i][i] = 0;
  }
  for(int l=2; l<=s.length(); ++l)
  {
    for(int s_ind=0; s_ind<=s.length()-l; ++s_ind)
    {
      if(s[s_ind] == s[s_ind+l-1])
        dynamic[s_ind][s_ind+l-1] = s_ind+1<=s_ind+l-2 ? dynamic[s_ind+1][s_ind+l-2] : 0;
      else
        dynamic[s_ind][s_ind+l-1] = 1 + min(dynamic[s_ind+1][s_ind+l-1], dynamic[s_ind][s_ind+l-2]);
    }
  }
  return dynamic[0][s.length()-1];
}

int main()
{
  string s;
  while(cin >> s)
  {
    cout << min_palindrome(s) << endl;
  }
}

import sys
def min_palindrome(s):
    if len(s) <= 1:
        return 0
    dynamic = [[0] * len(s)] * len(s)
    for l in xrange(2, len(s)+1):
        for s_ind in xrange(0, len(s)+1-l):
            if s[s_ind] == s[s_ind + l-1]:
                dynamic[s_ind][s_ind + l-1] = 0 if s_ind+1>s_ind + l-2 else dynamic[s_ind+1][s_ind + l-2]
            else:
                dynamic[s_ind][s_ind + l-1] = 1 + min(dynamic[s_ind+1][s_ind + l-1], dynamic[s_ind][s_ind + l-2])
    return dynamic[0][len(s)-1]
for line in sys.stdin:
    print min_palindrome(line.strip())

	import java.util.Scanner;



	



	public class ConstructPlalindrome {
    public static void main(String[] args) { 
        Scanner scan = new Scanner(System.in);
        
        while(scan.hasNext()) {
            String s = scan.nextLine();
            System.out.println(s);
            int len = lenghOfLCS(s, new StringBuffer(s).reverse().toString());
            System.out.println(s.length() - len);
        }
        
        scan.close();
    }

    //动态规划求最长公共子序列的长度
	public static int lenghOfLCS(String s1, String s2) {
		char[] ch1 = s1.toCharArray();
		char[] ch2 = s2.toCharArray();
		
		int n1 = s1.length();
		int n2 = s2.length();
		int[][] table = new int[n1][n2];//所有元素默认初始化为0
		
		if(ch1[0] == ch2[0]) table[0][0] = 1;
		
		//单独计算s2与s1首字母之间的的LCS长度
		for(int i = 1; i < n2; ++i) {
			if(ch1[0] == ch2[i])
				table[0][i] = 1;
			else
				table[0][i] = table[0][i-1];
		}
		
		//单独计算s1与s2首字母之间的LCS长度
		for(int i = 1; i < n1; ++i) {
			if(ch2[0] == ch1[i])
				table[i][0] = 1;
			else 
				table[i][0] = table[i-1][0];
		}
		
		//递推求解各个字符处的LCS
		for(int i = 1; i < n1; ++i) {
			for(int j = 1; j < n2; ++j) {
				if(ch1[i] == ch2[j]) {
					table[i][j] = table[i-1][j-1] + 1;
				}else
					table[i][j] = table[i-1][j] > table[i][j-1] ? table[i-1][j] : table[i][j-1];
			}
		}

		return table[n1-1][n2-1];
	}
}

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s1;
    int max_len[1001][1001];
    while(cin >> s1){
        string s2(s1.rbegin(), s1.rend());
        for(int i=0;i<=s1.length();i++)
            for(int j=0;j<=s2.length();j++){
                if(i==0 || j==0 )
                    max_len[i][j] = 0;
                else if(s1[i-1] == s2[j-1])
                    max_len[i][j] = max_len[i-1][j-1] + 1;
                else
                    max_len[i][j] = max(max_len[i-1][j] , max_len[i][j-1]);
            }
        cout << s1.length() - max_len[s1.length()][s2.length()] <<endl;
    }   
}

function Max(a,b){
	return a>b?a:b;
}
function find (str1) {
	var str2 = str1.split("");str2 = str2.reverse();str2 = str2.join("");
	var max = 0;
	var resArr = new Array(str1.length+1);
	for(var i = 0;i<=str1.length+1;i++){  //初始化
		resArr[i] = new Array(str2.length+1);
		for(var j = 0;j<=str2.length+1;j++){
			resArr[i][j] = 0;
		}
	}

	for(var i = 0;i<=str1.length;i++){
		for(var j = 0;j<=str2.length;j++){
			if(i==0||j==0){
				resArr[i][j] = 0;
			}else{
				if(str1[i-1] == str2[j-1]){
					resArr[i][j] = resArr[i-1][j-1]+1;//前一次循环中数组元素保存的值加1
				}else{
					resArr[i][j] = Max(resArr[i-1][j],resArr[i][j-1]);//不用连续
				}
			}
			if(max<resArr[i][j]){
				max = resArr[i][j];//保存最大的数，也就是匹配最长的长度
			}
		}
	}
	//输出结果
	if(max == 0){
		return str1.length;
	}else{
		return str1.length-max;
	}
}

function getCount(str){
    var strArr = str.split("");
    var strLen = 0;
    for(var i=0;i<strArr.length;i++){
        for(var j=strArr.length;j>=i;j--){
            if(strArr[i]==strArr[j]){
                var count = 1;
                var temp_i = i,temp_j = j;
                while(strArr[++temp_i]==strArr[--temp_j]){
                    if(temp_i<temp_j){//情况一
                    	count++;
                    }else if(temp_i == temp_j){//情况二
                    	count+=0.5;
                    }else{//防止死循环
                    	break;
                    }
                }
                if(temp_j>temp_i){//情况三
                	count+=0.5;
                }
               if(count>strLen){
                   strLen = count;
               }
            }
        }
    }
    return str.length-Math.floor(strLen*2);
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str =sc.nextLine();
            char[] strchar = str.toCharArray();
            int length= strchar.length;
            int[][] dp = new int[length][length];
            for(int j=1;j<length;j++){
                dp[j-1][j]=strchar[j-1]==strchar[j]?0:1;
                for(int i=j-2;i>-1;i--){
                    if(strchar[i]==strchar[j]){
                        dp[i][j]=dp[i+1][j-1];
                    }else{
                        dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                    }
                }
            }
        }
    }
}

pyhon使用DP的解决方案

import sys

def main():
    for line in sys.stdin:
        str1 = line[:-2]
        n = len(str1)
        str2 = str1[::-1]
        rec = [[0 for x in range(n+1)] for x in range(n+1)]
    for i in range(1,n+1):
            for j in range(1,n+1):
            if str1[j-1] == str2[i-1]:
                    rec[i][j] = rec[i-1][j-1] + 1
                else:
                    rec[i][j] = max(rec[i-1][j], rec[i][j-1])
    print n - rec[n][n]
main()

C++ 动态规划

#include <bits/stdc++.h>

using namespace std;

/*
dp[i][j]: i到j的最长回文子序列长度
1. s[i] = s[j], 则dp[i][j] = dp[i + 1][j - 1] + 2;
2. s[i] != s[j], dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
边界: dp[i][i] = 1;
*/
int main() {
    string s;
    int dp[1003][1003];
    while (cin >> s) {
        int n = s.size();
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        for (int j = 1; j < n; ++j) {
            for (int i = j - 1; i >= 0; --i) {
                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
        cout << n - dp[0][n - 1] << endl;
    }
    return 0;
}

开始用了递归，时间复杂度太高，改用了动态规划，通过。

/* 做题需要脑子，多分析思考。。
 * 多思考，问题会很简单。。。。
 * 数学分析。。。。。。。。。。 
 */
#include<stdio.h>
char s[1000];
int a[1000][1000];

int min( int x, int y)
{
    return x<y?x:y;
} 

//递归时间复杂度太高了，改用动态规划 
int func( int begin, int end)
{
    int i, k;
    for( k=1; k<end-begin+1; k++)
    {
        for( i=begin; i<end; i++)
        {
            if( s[i]==s[i+k]) a[i][i+k]=a[i+1][i+k-1];
            else a[i][i+k] = min( a[i][i+k-1], a[i+1][i+k])+1;
        }
    }
    return a[begin][end];
}

int main()
{
    int i=0, j, flag=0; char c;

    while(1)
    {
        for( i=0; (c=getchar())!=EOF; i++)
        {
            if( c=='\n') break;
            s[i]=c;
        }
        if( c==EOF) break;
        printf( "%d\n", func( 0, i-1));
    }

    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int solution(string s){
    int result;
        int n=s.length();
        int dp[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j]=0;
            }
        }
        for(int j=0;j<n;j++){
            dp[j][j]=1;
        }
        for(int j=1;j<n;j++){
            for(int k=0;k<n-j;k++){
                if(s[k]==s[k+j]){
                     dp[k][k+j]=dp[k+1][k+j-1]+2;
                }
                else{
                     dp[k][k+j]=max(dp[k+1][k+j],dp[k][k+j-1]);
                }
            }
        }
        result=n-dp[0][n-1];
    return result;
}
int main(){
    string s;
    while(cin>>s){
        cout<<solution(s)<<endl;
    }
    return 0;
}

int getGGZC(string s1,string s2){
vector<vector<int>> ss(s1.size(),vector<int>(s2.size(),0));


//初始化 如s1="abc" s2="acdeeee"。s1和s2首字母相等则
//ss[0][0](a,a)，ss[0][1](a,ac)，ss[0][2](a,acd)...
//ss[1][0](a,a),ss[2][0](ab,,a),ss[3][0](abc,a)...等最长公共子串都是1.
//首字母不等则都为0.
if(s1[0]==s2[0]){
for(int i=0;i<s1.size();i++){
ss[i][0]=1;
}
for(int j=0;j<s2.size();j++){
ss[0][j]=1;
}
}


//i,j分别表示s1和s2上字符的位置
//如 s1="abc" s2="acdeeee" ss[1][2]的值就是“ab”和“acd”的最大公共子串长
for(int i=1;i<s1.size();i++){
for(int j=1;j<s2.size();j++){
if(s1[i]==s2[j])ss[i][j]=ss[i-1][j-1]+1;
else{
ss[i][j]=max(ss[i-1][j],ss[i][j-1]);
}
}
}
int a=ss[s1.size()-1][s2.size()-1];

return a;

}

int main(){
string str;
while(cin>>str){

string ss=str;
reverse(ss.begin(),ss.end());

cout<<ss.size()-getGGZC(str,ss)<<endl;
}

return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] arg){
        Scanner input = new Scanner(System.in);
        while(input.hasNextLine()){
            String s = input.nextLine();
            char[] c = s.toCharArray();
            intlen  = c.length;
            int[][] state = new int[len+1][len+1];
            state[0][0] = 0;
            for(int i = 0; i < len; i++){   //正序的每一个字符同反序的每一个字符比较
                for(int j = 0; j < len; j++){
                    if(c[i] == c[len-1-j]) state[i+1][j+1] = state[i][j] + 1;  //字符是相同的  则前一个字符相同的数加一
                    else state[i+1][j+1] = Math.max(state[i+1][j],state[i][j+1]); //对应的字符不相同  则取前面相同字符数中最大那个
                    //这样得到就是相同字符数最多的值  就是回文的长度  总长减去此长  就得到要删减的数目
                }
            }
            System.out.println(len - state[len][len]);
        }
    }
}