求最少增加幾個字符可以將一個字符串變為回文子串，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]