区间动态规划例题：最小代价构造回文串问题

题目描述
给定一个字符串s，每次操作可以在任意位置插入一个字符，求将s变成回文串所需的最少插入次数。例如，字符串"ab"插入1次（变成"aba"或"bab"）即可成为回文串。

解题思路

1. 问题分析
   回文串的特点是正读反读相同。要使s成为回文串，需要保证s[i]和s[j]对称（即相等）。如果s[i] != s[j]，可以通过在某一侧插入字符使其匹配。
   关键思路：最少插入次数 = 字符串长度 - 最长回文子序列长度。因为最长回文子序列本身已是对称的，只需为剩余字符插入对称字符即可。

2. 动态规划定义
   定义dp[i][j]表示子串s[i:j+1]变成回文串的最小插入次数。目标是求dp[0][n-1]。

3. 状态转移方程

   • 如果s[i] == s[j]，两端字符已匹配，直接考虑内部子串：
     dp[i][j] = dp[i+1][j-1]（当j - i > 1时）
     特殊情况：当j - i <= 1时，若s[i] == s[j]，则dp[i][j] = 0（本身是回文）。
   • 如果s[i] != s[j]，有两种选择：
     1. 在j后插入s[i]，匹配s[i]和s[j+1]，代价为1 + dp[i+1][j]
     2. 在i前插入s[j]，匹配s[i-1]和s[j]，代价为1 + dp[i][j-1]
        取最小值：dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

4. 初始化与遍历顺序

   • 单个字符已是回文，初始化dp[i][i] = 0。
   • 需要从较短的区间向较长的区间递推，因此按区间长度len从小到大遍历。

详细步骤
以字符串s = "abac"为例：

1. 初始化dp表（4×4），对角线dp[i][i] = 0：

      a  b  a  c
   a  0  ?  ?  ?
   b     0  ?  ?
   a        0  ?
   c           0
   

2. 计算长度为2的区间：
   • [a,b]: s[0]!=s[1] → min(dp[1][1], dp[0][0]) + 1 = min(0,0)+1 = 1
   • [b,a]: s[1]!=s[2] → min(dp[2][2], dp[1][1]) + 1 = 1
   • [a,c]: s[2]!=s[3] → min(dp[3][3], dp[2][2]) + 1 = 1

      a  b  a  c
   a  0  1  ?  ?
   b     0  1  ?
   a        0  1
   c           0
   

3. 计算长度为3的区间：
   • [a,b,a]: s[0]==s[2] → dp[1][1] = 0（内部"b"已处理）
   • [b,a,c]: s[1]!=s[3] → min(dp[2][3], dp[1][2]) + 1 = min(1,1)+1 = 2

      a  b  a  c
   a  0  1  0  ?
   b     0  1  2
   a        0  1
   c           0
   

4. 计算整个字符串[a,b,a,c]：
   s[0]!=s[3] → min(dp[1][3], dp[0][2]) + 1 = min(2,0)+1 = 1
   最终结果：dp[0][3] = 1（只需插入1个字符，如末尾插入"a"得"abaca"）。

复杂度分析

• 时间复杂度：O(n²)，需要填充n×(n)的DP表。
• 空间复杂度：O(n²)，可优化至O(n)（仅存储上一行）。