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

字数 1477 2025-11-02 10:11:13

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

题目描述
给定一个字符串 s，你可以在任意位置插入任意字符，每次插入操作记为一次成本。要求计算出使字符串成为回文串所需的最小插入次数。与基础版不同，进阶版中允许插入的字符可以是任意字符，但目标是最小化总插入次数。例如，对于字符串 "abca"，最小插入次数为 1（在末尾插入 'a' 得到 "abcba"）。

解题过程

问题分析
回文串的特点是正读反读相同。若字符串 s 本身不是回文，需要通过插入字符使其对称。关键观察是：最小插入次数等于字符串长度减去其最长回文子序列（LPS）的长度。因为保留最长回文子序列后，只需为剩余字符插入对称字符即可。
定义状态
设 dp[i][j] 表示子串 s[i:j+1] 变成回文串所需的最小插入次数。目标是求 dp[0][n-1]，其中 n 为字符串长度。
状态转移方程
- 如果 s[i] == s[j]，则两端字符已匹配，直接考虑内部子串 s[i+1:j] 的插入次数：
  dp[i][j] = dp[i+1][j-1]（当 j > i+1 时）
  注意：当 j == i+1 时，两字符相邻且相等，无需插入，dp[i][j] = 0；当 j == i 时，单字符已是回文，dp[i][j] = 0。
- 如果 s[i] != s[j]，则需在左侧或右侧插入字符匹配另一端：
  - 在右侧插入 s[i] 匹配左端：成本为 1 + dp[i+1][j]（即忽略 s[i]，先处理 s[i+1:j+1]）。
  - 在左侧插入 s[j] 匹配右端：成本为 1 + dp[i][j-1]（即忽略 s[j]，先处理 s[i:j]）。
    取最小值：dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1。
初始化与遍历顺序
- 初始化：单个字符无需插入，即 dp[i][i] = 0。
- 遍历顺序：由于 dp[i][j] 依赖左下方（i+1）、左侧（j-1）的值，需按区间长度 len 从小到大的顺序计算（len 从 2 到 n）。
示例计算
以 s = "abca" 为例（n=4）：
- 初始化：所有 dp[i][i] = 0。
- 长度 2：
  - dp[0][1]：'a' != 'b'，min(dp[1][1], dp[0][0]) + 1 = min(0,0) + 1 = 1。
  - dp[1][2]：'b' != 'c'，min(dp[2][2], dp[1][1]) + 1 = 1。
  - dp[2][3]：'c' != 'a'，min(dp[3][3], dp[2][2]) + 1 = 1。
- 长度 3：
  - dp[0][2]：'a' != 'c'，min(dp[1][2], dp[0][1]) + 1 = min(1,1) + 1 = 2。
  - dp[1][3]：'b' != 'a'，min(dp[2][3], dp[1][2]) + 1 = min(1,1) + 1 = 2。
- 长度 4：dp[0][3]：'a' == 'a'，匹配两端，内部子串 dp[1][2] = 1，所以 dp[0][3] = 1。
  最终结果为 dp[0][3] = 1，与直观解法一致。
复杂度分析
时间复杂度 O(n²)，空间复杂度 O(n²)（可优化至 O(n)）。

区间动态规划例题：最小插入次数构造回文串问题（进阶版）题目描述给定一个字符串 s ，你可以在任意位置插入任意字符，每次插入操作记为一次成本。要求计算出使字符串成为回文串所需的最小插入次数。与基础版不同，进阶版中允许插入的字符可以是任意字符，但目标是最小化总插入次数。例如，对于字符串 "abca" ，最小插入次数为 1（在末尾插入 'a' 得到 "abcba" ）。解题过程问题分析回文串的特点是正读反读相同。若字符串 s 本身不是回文，需要通过插入字符使其对称。关键观察是：最小插入次数等于字符串长度减去其最长回文子序列（LPS）的长度。因为保留最长回文子序列后，只需为剩余字符插入对称字符即可。定义状态设 dp[i][j] 表示子串 s[i:j+1] 变成回文串所需的最小插入次数。目标是求 dp[0][n-1] ，其中 n 为字符串长度。状态转移方程如果 s[i] == s[j] ，则两端字符已匹配，直接考虑内部子串 s[i+1:j] 的插入次数： dp[i][j] = dp[i+1][j-1] （当 j > i+1 时）注意：当 j == i+1 时，两字符相邻且相等，无需插入， dp[i][j] = 0 ；当 j == i 时，单字符已是回文， dp[i][j] = 0 。如果 s[i] != s[j] ，则需在左侧或右侧插入字符匹配另一端：在右侧插入 s[i] 匹配左端：成本为 1 + dp[i+1][j] （即忽略 s[i] ，先处理 s[i+1:j+1] ）。在左侧插入 s[j] 匹配右端：成本为 1 + dp[i][j-1] （即忽略 s[j] ，先处理 s[i:j] ）。取最小值： dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 。初始化与遍历顺序初始化：单个字符无需插入，即 dp[i][i] = 0 。遍历顺序：由于 dp[i][j] 依赖左下方（ i+1 ）、左侧（ j-1 ）的值，需按区间长度 len 从小到大的顺序计算（ len 从 2 到 n ）。示例计算以 s = "abca" 为例（n=4）：初始化：所有 dp[i][i] = 0 。长度 2： dp[0][1] ： 'a' != 'b' ， min(dp[1][1], dp[0][0]) + 1 = min(0,0) + 1 = 1 。 dp[1][2] ： 'b' != 'c' ， min(dp[2][2], dp[1][1]) + 1 = 1 。 dp[2][3] ： 'c' != 'a' ， min(dp[3][3], dp[2][2]) + 1 = 1 。长度 3： dp[0][2] ： 'a' != 'c' ， min(dp[1][2], dp[0][1]) + 1 = min(1,1) + 1 = 2 。 dp[1][3] ： 'b' != 'a' ， min(dp[2][3], dp[1][2]) + 1 = min(1,1) + 1 = 2 。长度 4： dp[0][3] ： 'a' == 'a' ，匹配两端，内部子串 dp[1][2] = 1 ，所以 dp[0][3] = 1 。最终结果为 dp[0][3] = 1 ，与直观解法一致。复杂度分析时间复杂度 O(n²)，空间复杂度 O(n²)（可优化至 O(n)）。