LeetCode 1312: Minimum Insertion Steps to Make a String Palindrome (DP on Intervals)
English
Let dp[i][j] be the minimum insertions to make substring s[i..j] a palindrome. If s[i] == s[j], no extra insertion is needed at boundaries, so dp[i][j] = dp[i+1][j-1]. Otherwise we insert either near i or near j, giving dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1. Fill by increasing interval length.
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = (len == 2) ? 0 : dp[i + 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[0][n - 1];
}
}class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = 0 if length == 2 else dp[i + 1][j - 1]
else:
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
return dp[0][n - 1]中文
定义 dp[i][j] 表示把子串 s[i..j] 变成回文串所需的最少插入次数。若两端字符相等（s[i] == s[j]），边界不用新增字符，转移到 dp[i+1][j-1]；否则只能在左侧或右侧补字符，取较优方案再加一次插入：dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1。按区间长度从小到大填表即可。
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = (len == 2) ? 0 : dp[i + 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[0][n - 1];
}
}class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = 0 if length == 2 else dp[i + 1][j - 1]
else:
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
return dp[0][n - 1]