> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1001-2000/1312.-rang-zi-fu-chuan-cheng-wei-hui-wen-chuan-de-zui-shao-cha-ru-ci-shu.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`

```python
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]
```