区间动态规划例题：最小插入次数构造回文串问题（进阶版） 题目描述 给定一个字符串 s ，你可以在任意位置插入任意字符，每次插入操作记为一次代价。目标是使字符串变成回文串，并且要求最终回文串的长度恰好为 s.length() + k ，其中 k 是一个给定的非负整数。求满足条件的最小插入次数。如果无法构造长度为 s.length() + k 的回文串，则返回 -1。 解题思路 问题分析 ： 基础版本是只通过插入构造回文串，不限制最终长度。进阶版增加了长度约束，即最终回文串长度必须为 n + k 。 关键观察：若最终回文串长度固定，则原串中某些字符可能被跳过（不参与匹配），相当于在最终回文串中独立存在。 定义 dp[i][j][len] 表示将子串 s[i:j] 构成长度为 len 的回文串所需的最小插入次数。 状态转移 ： 考虑子串两端字符 s[i] 和 s[j] ： 若 s[i] == s[j] ，则这两个字符可以匹配，问题转化为 dp[i+1][j-1][len-2] 。 若 s[i] != s[j] ，则有两种选择： 在 j 后插入 s[i] ，匹配 i 和新插入的字符，问题变为 dp[i+1][j][len-2] + 1 。 在 i 前插入 s[j] ，匹配 j 和新插入的字符，问题变为 dp[i][j-1][len-2] + 1 。 此外，还可以跳过一端字符（即该字符在最终回文串中独立存在），此时长度仅减少1： 跳过 s[i] ： dp[i+1][j][len-1] 。 跳过 s[j] ： dp[i][j-1][len-1] 。 转移时取所有情况的最小值。 边界条件 ： 当 i > j 时，若 len == 0 ，则代价为0；若 len > 0 ，则需要插入 len 个字符（代价为 len ）。 当 i == j 时，若 len == 1 ，代价为0；若 len > 1 ，可跳过该字符或插入匹配字符，需具体讨论。 最终答案 ： 答案为 dp[0][n-1][n+k] ，若其值为无穷大则返回 -1。 示例 （ s = "abac" , k = 2 ）： 最终目标长度为 6，一种方案是插入字符后得到 "a b c b a c" （插入2次），但需检查是否为最优。 通过DP计算可得最小插入次数为2。 总结 本题通过三维DP灵活处理长度约束，核心在于状态定义涵盖子串和目