构造回文

"""
题目：给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。
突破口：碰到回文串，马上想到reverse。而对于回文串最长，可以考虑最长公共子序列。因此发现对原始串与reverse后的串寻找LCS，可以得到题解。
算法：
1. 构造reverse函数
2. 构造LCS函数
3. main函数求解，ret = 原字符串长度-lcs
"""


import sys


def LCS(s1, s2):
    row = col = len(s1)
    dp = [[0 for _ in range(col+1)] for _ in range(row+1)]
    for i in range(1, row+1):
        for j in range(1, col+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[row][col]


if __name__ == '__main__':
    for line in sys.stdin:
        s = line.strip()
        ret = len(s) - LCS(s, s[::-1])
        print(ret)

	

我用的python，一开妈用的递归，总是超时，后来反应过来要用动态规划，没来得及写完。
后来在错题里重做，总是有一个例子过不去，原来是输入的字符串里可能会有空格……，所以input()得到输入字符串之后要strip()一下。

def func(line):
    n = len(line)
    length = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        length[i][i] = 1
    for ll in range(1, n, 1):
        left = 0
        while left + ll < n:
            right = left + ll
            if line[left] == line[right]:
                length[left][right] = 2 + length[left + 1][right - 1]
            else:
                length[left][right] = max(length[left + 1][right], length[left][right - 1])
            left += 1
    return length[0][n - 1]


if __name__ == '__main__':
    while True:
        try:
            line = input().strip()
            n = len(line)
            print(n - func(line))
        except:
            break

# Python 版本 动态规划求解最长公共子序列
import sys
def LST(s1, s2):
    arr = []
    for _ in range(len(s1)+1):
        arr.append([0]*(len(s2)+1))
    
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            arr[i][j] = arr[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(arr[i-1][j], arr[i][j-1])
    
    return arr[len(s1)][len(s2)]

if __name__=="__main__":
    while True:
        s = sys.stdin.readline().strip()
        if not s:
            break
        print(len(s)-LST(s, s[::-1]))

差一点就内存超限了额(#手动滑稽)

def lcp(_line):
    """
    自己写的
    :param _line:
    :return:
    """
    _len = len(_line)
    if _line is None or _len == 0:  # 处理特殊值
        return 0
    dp = [[0] * (_len + 1) for i in range(_len + 1)]  # 动态规划
    for i in range(_len):  # 遍历求字符串与逆序的最大公共子序列
        for j in range(_len):
            if _line[i] == _line[_len - 1 - j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[_len][_len]
if __name__ == '__main__':
    while True:
        _line = sys.stdin.readline().strip()
        if not _line:
            break
        _res = lcp(_line)
        print(len(_line) - _res)

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 sys
try:
    while True:
        s = sys.stdin.readline().strip()
        if s == "":
            break
        strchar = list(s)
        length  = len(strchar)
        dp      = [[0]*length for i in range(length)]
        for j in range(length):
            #确定dp矩阵 次对角线的值。
            dp[j - 1][j] = 0 if strchar[j-1]==strchar[j] else 1
            for i in range(j-2, -1, -1):#i的取值范围为关键，递减从j-2到0
                #print i,j,"==="
                #根据次对角线的值，计算次次对角线的值，
                #若是前后匹配s[i]==s[j]，如abcda中的第一个a与最后一个a匹配，
                #那么只需要计算s[i+1]与s[j-1]之间的值了，如bcd字符串中需要进行比较的值
                #否则，计算min(dp[i+1][j], dp[i][j-1])+1
                #如，计算abcde，计算abcd与bcde，各自的dp值，在最小的方法上+1.
                if strchar[i] == strchar[j]:
                    dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = min(dp[i+1][j], dp[i][j-1])+1
#                for p in dp:
#                    print p
        print dp[0][-1]
except:
    pass

s = "abcda"
strchar = list(s)
length  = len(strchar)
dp      = [[0]*length for i in range(length)]
for j in range(length):
    dp[j - 1][j] = 0 if strchar[j-1]==strchar[j] else 1
    for i in range(j-2, -1, -1):
        print i,j,"==="
        if strchar[i] == strchar[j]:
            dp[i][j] = dp[i+1][j-1]
        else:
            dp[i][j] = min(dp[i+1][j], dp[i][j-1])+1
        for p in dp:
            print p