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

题目描述

给定一个字符串s，你可以在字符串的任意位置插入任意字符。要求计算最少插入次数，使得字符串变成回文串。

例如：

• 输入："ab"

• 输出：1（插入一个'b'变成"bab"，或插入一个'a'变成"aba"）

• 输入："abc"

• 输出：2（插入"cb"变成"abcba"）

解题思路

这个问题可以用区间动态规划解决。定义dp[i][j]表示将子串s[i...j]变成回文串所需的最小插入次数。

详细解题步骤

1. 状态定义

   • dp[i][j]：将子串s[i...j]变成回文串的最小插入次数
   • 目标：求dp[0][n-1]，其中n是字符串长度

2. 边界情况

   • 当i = j时，单个字符本身就是回文，插入次数为0
   • 当i > j时，空字符串，插入次数为0

3. 状态转移方程

   • 如果s[i] = s[j]：

     • 两端的字符相同，不需要额外插入
     • dp[i][j] = dp[i+1][j-1]

   • 如果s[i] ≠ s[j]：

     • 两种选择：
       1. 在j后面插入s[i]，匹配s[i]和s[j+1]
       2. 在i前面插入s[j]，匹配s[i-1]和s[j]
     • dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

4. 计算顺序

   • 从小区间到大区间计算
   • 按子串长度从小到大遍历

具体示例分析

以字符串"abca"为例：

1. 初始化dp表格：

   • 对角线dp[i][i] = 0（单个字符）
   • 上三角部分（i > j）为0

2. 计算长度为2的子串：

   • "ab"：s[0]≠s[1]，dp[0][1] = min(dp[1][1], dp[0][0]) + 1 = min(0,0) + 1 = 1
   • "bc"：s[1]≠s[2]，dp[1][2] = min(dp[2][2], dp[1][1]) + 1 = 1
   • "ca"：s[2]≠s[3]，dp[2][3] = min(dp[3][3], dp[2][2]) + 1 = 1

3. 计算长度为3的子串：

   • "abc"：s[0]≠s[2]
     • dp[0][2] = min(dp[1][2], dp[0][1]) + 1 = min(1,1) + 1 = 2
   • "bca"：s[1]≠s[3]
     • dp[1][3] = min(dp[2][3], dp[1][2]) + 1 = min(1,1) + 1 = 2

4. 计算长度为4的子串：

   • "abca"：s[0]=s[3]='a'
     • dp[0][3] = dp[1][2] = 1

最终结果为1，只需要插入1个字符。

算法实现

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(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(1)时间
• 总时间复杂度：O(n²)
• 空间复杂度：O(n²)

这个算法通过区间动态规划，系统地解决了最小插入构造回文串问题，保证了最优解的正确性。