区间动态规划例题：最小插入次数构造回文串问题

题目描述
给定一个字符串 s，你可以在任意位置插入任意字符，要求通过最少的插入次数，使字符串变成回文串。返回最小插入次数。

示例

• 输入：s = "ab"，输出：1（插入 "a" 或 "b"，例如 "aba" 或 "bab"）
• 输入：s = "abc"，输出：2（例如插入后得到 "abcba"，需插入 "b" 和 "c"）

解题思路

1. 问题分析
回文串的特点是正读反读相同。若 s 本身不是回文，我们需要通过插入字符使其对称。
关键观察：

• 如果 s[i] == s[j]，则两端字符已匹配，无需额外操作，只需考虑内部子串 [i+1, j-1]。
• 如果 s[i] != s[j]，有两种策略：
  1. 在 j 后面插入一个与 s[i] 相同的字符，匹配 s[i] 和新增字符，然后处理 [i+1, j]。
  2. 在 i 前面插入一个与 s[j] 相同的字符，匹配 s[j] 和新增字符，然后处理 [i, j-1]。
     每次插入操作计数一次，取两种策略的最小值。

2. 定义状态
设 dp[i][j] 表示将子串 s[i:j]（闭区间）变成回文串所需的最小插入次数。
目标：求 dp[0][n-1]，其中 n 是字符串长度。

3. 状态转移方程

• 当 s[i] == s[j]：
  dp[i][j] = dp[i+1][j-1]（两端已匹配，直接继承内部结果）
• 当 s[i] != s[j]：
  dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
  解释：
  • dp[i+1][j] 表示在 j 后插入 s[i] 匹配左端，然后处理 [i+1, j]。
  • dp[i][j-1] 表示在 i 前插入 s[j] 匹配右端，然后处理 [i, j-1]。

4. 初始化与边界条件

• 单个字符本身就是回文，插入次数为 0：dp[i][i] = 0。
• 空子串（i > j）不存在，但代码中不会访问，可忽略。
• 两个字符时：若相等则 dp[i][i+1] = 0，否则为 1。

5. 计算顺序
由于 dp[i][j] 依赖 i+1 和 j-1，需从小区间向大区间计算：

• 按区间长度 len 从小到大遍历（len 从 2 到 n）。
• 对于每个 len，遍历起始点 i，计算 j = i + len - 1。

逐步计算示例（s = "abc"）

步骤 1：初始化

• dp[0][0] = 0, dp[1][1] = 0, dp[2][2] = 0（单个字符）

步骤 2：长度为 2 的子串

• [0,1]：s[0]='a', s[1]='b'，不相等 → dp[0][1] = min(dp[1][1], dp[0][0]) + 1 = min(0,0) + 1 = 1
• [1,2]：s[1]='b', s[2]='c'，不相等 → dp[1][2] = min(dp[2][2], dp[1][1]) + 1 = 1

步骤 3：长度为 3 的子串 [0,2]

• s[0]='a', s[2]='c'，不相等 →
  dp[0][2] = min(dp[1][2], dp[0][1]) + 1 = min(1, 1) + 1 = 2

结果：最小插入次数为 2，与示例一致。

算法实现（Python）

def minInsertions(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):  # 子串长度
        for i in range(0, n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] if i+1 <= j-1 else 0
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
    return dp[0][n-1]

复杂度分析

• 时间复杂度：O(n²)
• 空间复杂度：O(n²)（可优化为 O(n)）

总结
本题通过区间 DP 将问题分解为子串的回文构造问题，核心在于处理两端字符是否匹配，并通过插入操作逐步逼近最优解。