1312.让字符串成为回文串的最少插入次数.md

1312. 让字符串成为回文串的最少插入次数

https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

解法一：dp

与516. 最长回文子序列类似 用dp[i][j]表示s[i...j]变成回文串需要的插入次数 当s[i] == s[j]时，回文串s[i+1...j-1]变成s[i...j]不需要插入，即dp[i][j] = dp[i+1][j-1] 当s[i] != s[j]时，s[i...j]要成为回文，可以由回文s[i+1...j]在右侧插入s[i]，或回文s[i...j-1]在左侧插入s[j]。即dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

class Solution:
    def minInsertions(self, s: str) -> int:
        n=len(s)
        if n==1:
            return 0
        dp=[[0]*n for i in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if i == j:
                    dp[i][j] = 0
                    continue
                if s[i] == s[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[0][n-1]