区间动态规划例题：最小成本构造回文串问题（字符插入、删除、替换的通用版本）
字数 1625 2025-12-05 06:40:36

区间动态规划例题：最小成本构造回文串问题（字符插入、删除、替换的通用版本）

题目描述
给定一个字符串 s 和一个成本表，包含三种操作的成本：

  1. 插入一个字符，成本为 insertCost。
  2. 删除一个字符，成本为 deleteCost。
  3. 替换一个字符为另一个字符，成本为 replaceCost（若字符相同，成本为0）。
    要求通过若干次操作将 s 转化为回文串，求最小总成本。

示例
输入：s = "abac"，insertCost = 2，deleteCost = 3，replaceCost = 4。
输出：最小成本为 4（将 'c' 替换为 'b'，成本为4）。

解题思路

  1. 定义状态
    设 dp[i][j] 表示将子串 s[i:j]（左闭右闭区间）转化为回文串的最小成本。

  2. 状态转移

    • 情况1：若 s[i] == s[j]，两端字符已匹配，直接处理内部子串：
      dp[i][j] = dp[i+1][j-1]。
    • 情况2：若 s[i] != s[j]，需通过操作使两端匹配，考虑三种策略：
      1. 在末尾插入一个与 s[i] 相同的字符，匹配后删除 s[i]（等效于直接删除 s[i]）：
        cost1 = deleteCost + dp[i+1][j]。
      2. 在开头插入一个与 s[j] 相同的字符，匹配后删除 s[j]（等效于直接删除 s[j]）：
        cost2 = deleteCost + dp[i][j-1]。
      3. 替换一端字符：
        • 将 s[i] 替换为 s[j]：cost3 = replaceCost + dp[i+1][j-1]。
        • 将 s[j] 替换为 s[i]：与上等价，取最小值即可。
          dp[i][j] = min(cost1, cost2, cost3)。

  3. 边界条件

    • 空串或单字符已是回文，成本为0：
      dp[i][i] = 0（单字符）。
      dp[i][j] = 0（当 i > j，空子串）。

  4. 计算顺序
    按区间长度 len 从小到大的顺序计算，确保子问题先被解决。

详细计算步骤
以 s = "abac" 为例（insertCost=2, deleteCost=3, replaceCost=4）：

  1. 初始化：所有单字符成本为0，即 dp[0][0]=dp[1][1]=dp[2][2]=dp[3][3]=0。
  2. 长度为2的子串：
    • "ab"：
      • 删除 'a'：3 + dp[1][1] = 3
      • 删除 'b'：3 + dp[0][0] = 3
      • 替换 'a' 为 'b'（或反向）：4 + dp[1][0]（空串）= 4
        dp[0][1] = min(3, 3, 4) = 3。
    • 同理计算其他长度为2的子串。
  3. 长度为3的子串：
    • "aba"：两端字符相同，dp[0][2] = dp[1][1] = 0。
    • "bac"：
      • 删除 'b'：3 + dp[1][2]（需先计算 "ac" 的成本）
      • 逐步递推后取最小值。
  4. 最终区间 [0,3]：
    • 两端 'a' 和 'c' 不同，比较三种操作：
      • 删除 'a'：3 + dp[1][3]
      • 删除 'c'：3 + dp[0][2] = 3 + 0 = 3
      • 替换 'c' 为 'a'：4 + dp[1][2]
        经计算 dp[0][3] = 4（选择替换操作）。

关键点

  • 操作可相互转化（如插入+删除等效于替换），但成本不同，需比较三者。
  • 若 replaceCost > insertCost + deleteCost，可能优先选择插入+删除组合。
  • 时间复杂度 O(n²)，空间复杂度 O(n²)（可优化为 O(n)）。

通过以上步骤，可逐步推导出任意字符串的最小构造回文成本。

区间动态规划例题：最小成本构造回文串问题（字符插入、删除、替换的通用版本） 题目描述 给定一个字符串 s 和一个成本表，包含三种操作的成本： 插入 一个字符，成本为 insertCost 。 删除 一个字符，成本为 deleteCost 。 替换 一个字符为另一个字符，成本为 replaceCost （若字符相同，成本为0）。 要求通过若干次操作将 s 转化为回文串，求最小总成本。 示例 输入： s = "abac" ， insertCost = 2 ， deleteCost = 3 ， replaceCost = 4 。 输出：最小成本为 4（将 'c' 替换为 'b' ，成本为4）。 解题思路 定义状态 设 dp[i][j] 表示将子串 s[i:j] （左闭右闭区间）转化为回文串的最小成本。 状态转移 情况1 ：若 s[i] == s[j] ，两端字符已匹配，直接处理内部子串： dp[i][j] = dp[i+1][j-1] 。 情况2 ：若 s[i] != s[j] ，需通过操作使两端匹配，考虑三种策略： 在末尾插入一个与 s[i] 相同的字符 ，匹配后删除 s[i] （等效于直接删除 s[i] ）： cost1 = deleteCost + dp[i+1][j] 。 在开头插入一个与 s[j] 相同的字符 ，匹配后删除 s[j] （等效于直接删除 s[j] ）： cost2 = deleteCost + dp[i][j-1] 。 替换一端字符 ： 将 s[i] 替换为 s[j] ： cost3 = replaceCost + dp[i+1][j-1] 。 将 s[j] 替换为 s[i] ：与上等价，取最小值即可。 dp[i][j] = min(cost1, cost2, cost3) 。 边界条件 空串或单字符已是回文，成本为0： dp[i][i] = 0 （单字符）。 dp[i][j] = 0 （当 i > j ，空子串）。 计算顺序 按区间长度 len 从小到大的顺序计算，确保子问题先被解决。 详细计算步骤 以 s = "abac" 为例（ insertCost=2, deleteCost=3, replaceCost=4 ）： 初始化 ：所有单字符成本为0，即 dp[0][0]=dp[1][1]=dp[2][2]=dp[3][3]=0 。 长度为2的子串 ： "ab" ： 删除 'a' ： 3 + dp[1][1] = 3 删除 'b' ： 3 + dp[0][0] = 3 替换 'a' 为 'b' （或反向）： 4 + dp[1][0]（空串）= 4 dp[0][1] = min(3, 3, 4) = 3 。 同理计算其他长度为2的子串。 长度为3的子串 ： "aba" ：两端字符相同， dp[0][2] = dp[1][1] = 0 。 "bac" ： 删除 'b' ： 3 + dp[1][2] （需先计算 "ac" 的成本） 逐步递推后取最小值。 最终区间 [0,3] ： 两端 'a' 和 'c' 不同，比较三种操作： 删除 'a' ： 3 + dp[1][3] 删除 'c' ： 3 + dp[0][2] = 3 + 0 = 3 替换 'c' 为 'a' ： 4 + dp[1][2] 经计算 dp[0][3] = 4 （选择替换操作）。 关键点 操作可相互转化（如插入+删除等效于替换），但成本不同，需比较三者。 若 replaceCost > insertCost + deleteCost ，可能优先选择插入+删除组合。 时间复杂度 O(n²)，空间复杂度 O(n²)（可优化为 O(n)）。 通过以上步骤，可逐步推导出任意字符串的最小构造回文成本。