1312：让字符串成为回文串的最少插入次数（1786 分）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        f = [[0]*n for _ in range(n)]
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                if s[i]==s[j]:
                    f[i][j] = f[i+1][j-1]
                else:
                    f[i][j] = 1+min(f[i+1][j],f[i][j-1])
        return f[0][-1]