（1）先求出最少需要添加多少个字符串才能补成回文串？
str的长度为N，生成N×N的dp矩阵，dp[i][j]的含义是子串str[i…j]最少添加几个字符可以使str[i…j]整体都是回文串。dp[i][j]的求法如下：
（2）根据求得的dp矩阵来获得一种回文结果：【类似最长公共子序列】
dp[0][N-1]的值代表整个字符串最少需要添加几个字符，所以，如果最后的结果记为字符串res，res的长度为 N + dp[0][N-1]，然后依次设置res左右两头的字符。
def getPalindrome(str1):
def getdp(str1):
dp = [[0 for i in range(len(str1))] for j in range(len(str1))]
for j in range(1, len(str1)):
dp[j-1][j] = 0 if str1[j-1] == str1[j] else 1
for i in range(j-2, -1, -1):
if str1[i] == str1[j]:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
return dp
if str1 == None or len(str1) < 2:
return str1
dp = getdp(str1)
res = [0 for i in range(len(str1)+dp[0][len(str1)-1])]
i = 0
j = len(str1) - 1
resl = 0
resr = len(res) - 1
while i <= j:
if str1[i] == str1[j]:
res[resl] = str1[i]
res[resr] = str1[j]
i += 1
j -= 1
elif dp[i+1][j] < dp[i][j-1]:
res[resl] = str1[i]
res[resr] = str1[i]
i += 1
else:
res[resl] = str1[j]
res[resr] = str1[j]
j -= 1
resl += 1
resr -= 1
return ‘‘.join(res)
str = ‘A1BC22D1EF’ , str1 = ‘1221‘，先剥1。A----1BC22D1------EF，1的外壳是left= A,right = EF,则左边补（right逆序+left），右边补（left逆序+right）。即FEA----1BC22D1-------AEF。
第二层为2，：FEA1----BC------22-------D----1AEF，left=BC，right= D。同理。
def getPalindrome2(str1, strlps):
if str1 == None or len(str1) == 0 or strlps == None or len(strlps) == 0:
return
res = [0 for i in range(2*len(str1)-len(strlps))]
lstr = 0
rstr = len(str1)-1
llps = 0
rlps = len(strlps)-1
lres = 0
rres = len(res)-1
while llps <= rlps:
temp1 = lstr
temp2 = rstr
while str1[lstr] != strlps[llps]:
lstr += 1
while str1[rstr] != strlps[rlps]:
rstr -= 1
for i in range(temp1, lstr):
res[lres] = str1[i]
res[rres] = str1[i]
lres += 1
rres -= 1
for i in range(temp2, rstr, -1):
res[lres] = str1[i]
res[rres] = str1[i]
lres += 1
rres -= 1
res[lres] = str1[lstr]
res[rres] = str1[rstr]
lstr += 1
rstr -= 1
lres += 1
rres -= 1
llps += 1
rlps -= 1
return ‘‘.join(res)
给定一个字符串str,返回把str全部切成回文子串的最小分割数。
定义动态规划数组dp，dp[i]的含义是子串str[0…i]至少需要切割几次，才能把str[0…i]全部切成回文子串。那么dp[len-1]就是最后的结果。
import sys
#从前往后遍历
def minCut(str1):
if str1 == None or str1 == "":
return 0
N = len(str1)
p = [[False for i in range(N)] for j in range(N)]
dp = [0 for i in range(N)]
for i in range(N):
dp[i] = sys.maxsize
for j in range(i, -1, -1):
if str1[j] == str1[i] and (i-j < 2 or p[j+1][i-1]):
p[j][i] = True
dp[i] = min(dp[i], 0 if j-1 == -1 else dp[j-1] + 1)
return dp[-1]
原文：https://www.cnblogs.com/Lee-yl/p/10461472.html