求最少增加几个字符可以将一个字符串变为回文子串，DP，结果=原字符串长度-最长回文子串长度，方法同516题（回文子串的定义是可以取不连续的字符）
1 #1312
2 #Runtime: 398 ms (Beats 94.87%)
3 #Memory: 15 MB (Beats 94.87%)
4
5 class Solution(object):
6 def minInsertions(self, s):
7 """
8 :type s: str
9 :rtype: int
10 """
11 n = len(s)
12 dp = [[0] * n for _ in range(n)]
13 for i in range(n - 1, -1, -1):
14 dp[i][i] = 1
15 for j in range(i + 1, n):
16 if s[i] == s[j]:
17 dp[i][j] = dp[i + 1][j - 1] + 2
18 else:
19 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
20 return len(s) - dp[0][n-1]