区间动态规划例题：最小插入次数构造回文串问题（进阶版） 题目描述 给定一个字符串 s ，你可以在任意位置插入任意字符，求最少插入次数，使得字符串成为回文串。例如，对于 s = "abca" ，最少插入次数为 1（插入 b 后变为 "abcba" ）。 解题思路 本题是区间动态规划的经典应用。定义 dp[i][j] 表示将子串 s[i..j] 变为回文串所需的最少插入次数。通过分析子串两端字符是否相等，逐步缩小问题规模。 详细步骤 状态定义 设 dp[i][j] 表示将子串 s[i..j] 变成回文串的最小插入次数。目标是求解 dp[0][n-1] ，其中 n 是字符串长度。 边界条件 当 i == j 时，子串长度为 1，本身是回文，插入次数为 0： dp[i][i] = 0 。 当 i > j 时，视为空串，插入次数为 0（实际不会发生，但需保证逻辑正确）。 状态转移方程 如果 s[i] == s[j] ，两端字符相同，则整个子串的最小插入次数等于内部子串 s[i+1..j-1] 的插入次数： dp[i][j] = dp[i+1][j-1] 。 如果 s[i] != s[j] ，两端字符不同，有两种操作选择： 在 j 右侧插入 s[i] ，使 s[i] 和新增字符匹配，问题转化为 s[i+1..j] 的插入次数加 1。 在 i 左侧插入 s[j] ，使 s[j] 和新增字符匹配，问题转化为 s[i..j-1] 的插入次数加 1。 取两种情况的最小值： dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 。 计算顺序 由于 dp[i][j] 依赖于 dp[i+1][j-1] 、 dp[i+1][j] 和 dp[i][j-1] ，需要从较短的子串向较长的子串计算。按子串长度 len 从 2 到 n 遍历，再遍历起始下标 i 。 示例演算 以 s = "abca" 为例（n=4）： 初始化：所有 dp[i][i] = 0 。 长度 len=2 ： "ab" ： s[0] != s[1] ， dp[0][1] = min(dp[1][1], dp[0][0]) + 1 = 1 。 "bc" ：同理得 dp[1][2] = 1 。 "ca" ： dp[2][3] = 1 。 长度 len=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 = 2 。 长度 len=4 ： "abca" ： s[0] == s[3] （均为 'a' ）， dp[0][3] = dp[1][2] = 1 。 最终结果为 dp[0][3] = 1 。 复杂度分析 时间复杂度：O(n²)，需要填充 n×(n+1)/2 个状态。 空间复杂度：O(n²)，可用滚动数组优化至 O(n)。