与牛客CD124题目一致
题目描述：给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。
示例：
输入：“zzazz” 输出：“zzazz”
输入：“abca” 输出：“acbca”
分析：
将此题目分为两步，首先是找到使字符串成为回文串的最少插入次数，再找到合适的位置插入字符即可。
第一步：
- 动态规划：当前字符串要变成回文,那只要把不一样的找出来就可以。则求出反转的字符串和当前字符串的最长公共子序列，原字符串长度减去最长公共子序列字符串长度即可。此方法求解整个dp表自顶向下需要完全遍历。
- 区间动态规划：
dp[L][R]表示对于字符串 s 的子串s[L:R]（L、R表示左右结尾字符），最少添加的字符数量，使得s[L:R]变为回文串。因此可以从外向内对dp表进行求解，分两种情况：
1、s[L] == s[R]，那么最外层已经形成了回文，则向内继续求解s[L+1:R-1]
2、s[L] != s[R]，则需要在s[L:R]的末尾添加字符s[L]，向内求解s[L+1:R]；或者是在s[L:R]的开头添加字符s[R]，向内求解s[L:R-1]
状态转移方程：
dp[L][R] = min(dp[L + 1][R] + 1, dp[L][R - 1] + 1) if s[L] != s[R]
dp[L][R] = dp[L+ 1][R - 1] if s[L] == s[R]
为了保证在计算 dp[L][R] 时，状态转移方程中的状态 dp[L + 1][R]，dp[L][R - 1] 和 dp[L + 1][R - 1] 均已计算过，使用自底向上的遍历方式，L从右往左遍历，R从L+1的位置开始向右遍历，因为L==R时表示单个字符不需要添加任何字符串即可构成回文串，初始化的时候初始为0。
第二步：
首先凑出原字符串长度+需要添加长度的字符数组res，原字符串s和结果字符串res同时从两边向内收缩， i, j = 0, n-1; l, r = 0, res_len - 1，
如果：原字符串两边相同 s[i] == s[j] 则给结果字符串两边都添加上这个相同的字符res[l] = res[r] = s[j]；
否则：比较dp[i+1][j] 和 dp[i][j-1]需要添加的字符串个数，用更短的来拼凑res[l] = res[r] = s[i]（或s[j]）
整体代码：
def minInsertions(s):n = len(s)dp = [[0]*n for _ in range(n)]for L in range(n-1, -1, -1): # L依赖于L+1 <----从右往左for R in range(L+1, n): # R依赖于R-1 ---->从左往右if s[L] == s[R]:dp[L][R] = dp[L+1][R-1]else:dp[L][R] = min(dp[L+1][R], dp[L][R-1]) + 1i, j = 0, n-1res_len = n + dp[0][n-1]l, r = 0, res_len - 1res = [0] * res_lenwhile i <= j:if s[i] == s[j]:res[l] = s[i]res[r] = s[j]l += 1;i += 1;r -= 1;j -= 1elif dp[i+1][j] < dp[i][j-1]:res[l] = res[r] = s[i]l += 1;i += 1;r -= 1else:res[l] = res[r] = s[j]l += 1;j -= 1;r -= 1return ress = input()
print(minInsertions(s))