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

## 1、题目描述¶

「回文串」是正读和反读都相同的字符串。

输入：s = "zzazz"



输入：s = "mbadm"



输入：s = "leetcode"



输入：s = "g"



输入：s = "no"



• 1 <= s.length <= 500
• s 中所有字符都是小写字母。

## 2、解题思路¶

• 动态规划

dp[i][j] 表示从i到j最短需要插入多少字符


if i == j:
dp[i][j] = 0
else:
if s[i] == s[j]:
if i + 1 == j:
dp[i][j] = 0
else:
dp[i][j] = dp[i + 1][j - 1]
else:
if i + 1 == j:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i + 1][j - 1] + 2)

class Solution:
def minInsertions(self, s: str) -> int:

length = len(s)
if length <= 1:
return 0

dp = [[length for _ in range(length)] for _ in range(length)]
for gap in range(length - 1):
for i in range(length - gap):
j = i + gap
if i == j:
dp[i][j] = 0
else:
if s[i] == s[j]:
if i + 1 == j:
dp[i][j] = 0
else:
dp[i][j] = dp[i + 1][j - 1]
else:
if i + 1 == j:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i + 1][j - 1] + 2)

if length - 1 == 1:
if s[0] == s[length - 1]:
return 0
else:
return 1
else:
if s[0] == s[length - 1]:
return dp[1][length - 2]
else:
return min(dp[0][length - 2] + 1, dp[1][length - 1] + 1, dp[1][length - 2] + 2)