区间动态规划例题：最小插入次数构造回文串问题（带字符替换成本） 题目描述 给定一个字符串 s ，你可以在任意位置插入任意字符，每次插入操作的成本为 insertCost 。此外，你还可以替换字符串中的任意字符，每次替换操作的成本为 replaceCost 。你的目标是通过最少的操作成本将 s 转换为回文串。请计算最小的总成本。 解题思路 我们使用区间动态规划来解决这个问题。定义 dp[i][j] 表示将子串 s[i..j] 转换为回文串所需的最小成本。我们需要考虑字符串两端的字符是否相等，以及是否通过插入或替换操作来调整。 详细步骤 状态定义 设 dp[i][j] 为将子串 s[i..j] 变成回文的最小成本。 初始时，若子串长度为 1（即 i == j ），它已经是回文，成本为 0。 若子串长度为 2（即 j == i+1 ），则根据两字符是否相等决定成本：相等则为 0，否则为 min(replaceCost, 2 * insertCost) （替换一个字符或插入两个字符）。 状态转移 对于每个区间 [i, j] ： 情况1 ： s[i] == s[j] 两端字符已匹配，直接继承内部子串的成本： dp[i][j] = dp[i+1][j-1] 情况2 ： s[i] != s[j] 此时有三种策略： a. 替换左端字符 ，使其与右端匹配：成本为 replaceCost + dp[i+1][j-1] b. 替换右端字符 ，使其与左端匹配：成本为 replaceCost + dp[i+1][j-1] （与a对称） c. 插入字符 ： 在右端插入一个与 s[i] 相同的字符：成本为 insertCost + dp[i+1][j] 在左端插入一个与 s[j] 相同的字符：成本为 insertCost + dp[i][j-1] 综合取最小值： dp[i][j] = min(replaceCost + dp[i+1][j-1], insertCost + dp[i+1][j], insertCost + dp[i][j-1]) 边界条件 当 i > j 时，子串为空，成本为 0。 当 i == j 时，子串长度为 1，成本为 0。 计算顺序 按子串长度从小到大遍历： 先遍历长度为 2 的子串，然后长度递增，直到整个字符串 s[0..n-1] 。 最终答案 dp[0][n-1] 即为将整个字符串转换为回文的最小成本。 示例 设 s = "ab" ， insertCost = 1 ， replaceCost = 2 ： 长度2： s[0] != s[1] ， dp[0][1] = min(2 + dp[1][0], 1 + dp[1][1], 1 + dp[0][0]) = min(2+0, 1+0, 1+0) = 1 最小成本为 1（插入一个字符，如 "aba" 或 "bab" ）。 通过以上步骤，你可以逐步计算出任意字符串的最小成本回文转换方案。