合并相邻字符的最小成本问题（字符删除、替换、插入的加权版本）

字数 2601 2025-12-09 22:31:44

合并相邻字符的最小成本问题（字符删除、替换、插入的加权版本）

题目描述
给定一个字符串 s 和一个字符集（例如小写字母），以及三种操作的成本：

删除任意位置的一个字符，代价为 deleteCost；
替换任意位置的一个字符为另一个字符，代价为 replaceCost；
插入任意位置插入一个字符，代价为 insertCost。

目标是通过一系列操作，将字符串 s 变成一个回文串，并且总代价最小。注意，这里的替换操作只能将一个字符替换为另一个字符，不允许替换为空或从空替换。

解题思路
这是一个区间动态规划问题。我们考虑字符串 s 的某个子串 s[i..j]（下标从 i 到 j），定义 dp[i][j] 为将该子串变成回文串的最小代价。
最终答案是 dp[0][n-1]，其中 n 是字符串长度。

状态转移思路：
对于子串 s[i..j]，我们考虑其两端的字符 s[i] 和 s[j]：

如果 s[i] == s[j]，两端字符已经相等，那么我们可以直接考虑内部子串 s[i+1..j-1] 变成回文的代价，即 dp[i][j] = dp[i+1][j-1]。
如果 s[i] != s[j]，我们需要通过操作使两端相等，有几种方案：
- 删除左端，让 s[i+1..j] 变成回文，然后删除 s[i]，代价 = dp[i+1][j] + deleteCost。
- 删除右端，让 s[i..j-1] 变成回文，然后删除 s[j]，代价 = dp[i][j-1] + deleteCost。
- 替换左端为 s[j]，使两端相等，然后处理内部 s[i+1..j-1]，代价 = dp[i+1][j-1] + replaceCost。
- 替换右端为 s[i]，同理代价 = dp[i+1][j-1] + replaceCost（注意替换左右端代价相同，因为 replaceCost 是固定的）。
- 插入一个字符在左端，让它与 s[j] 相等，这样原来的 s[i..j] 就变成 s[i..j] 加上新字符，但新字符与 s[j] 配对，相当于处理 s[i..j-1] 变成回文，然后插入一个字符，代价 = dp[i][j-1] + insertCost。
- 插入一个字符在右端，同理代价 = dp[i+1][j] + insertCost。

实际上，由于对称性，我们可以简化：

删除左端与插入右端效果类似，但代价可能不同（deleteCost vs insertCost）。
替换左端与替换右端代价相同。

因此，我们取这些方案的最小值。

边界条件：

当 i == j 时，子串长度为 1，它已经是回文，代价为 0。
当 i > j 时，空串，代价为 0。

计算顺序：
由于 dp[i][j] 依赖于 dp[i+1][j]、dp[i][j-1]、dp[i+1][j-1]，即依赖于更短的区间，我们可以按区间长度从小到大计算。

详细步骤

初始化一个二维数组 dp[n][n]，所有值设为 0。
先处理长度为 1 的区间：dp[i][i] = 0。
对于区间长度 len 从 2 到 n：
- 对于每个起点 i，计算终点 j = i + len - 1。
- 如果 s[i] == s[j]：
  - 如果 len == 2，则 dp[i][j] = 0（两个相同字符已经是回文）；
  - 否则 dp[i][j] = dp[i+1][j-1]。
- 如果 s[i] != s[j]：
  - 方案1：删除左端 -> dp[i+1][j] + deleteCost
  - 方案2：删除右端 -> dp[i][j-1] + deleteCost
  - 方案3：替换左端或右端 -> dp[i+1][j-1] + replaceCost
  - 方案4：在左端插入与 s[j] 相同的字符 -> dp[i][j-1] + insertCost
  - 方案5：在右端插入与 s[i] 相同的字符 -> dp[i+1][j] + insertCost
  - 取上述五种方案的最小值赋给 dp[i][j]。
最终 dp[0][n-1] 即为答案。

示例说明

假设 s = "abca", deleteCost = 3, replaceCost = 2, insertCost = 4。

n = 4
len=1: 全 0
len=2:
- [0,1] "ab"：不等
  删除左(3+dp[1][1]=3) = 3
  删除右(3+0)=3
  替换(2+dp[1][0]=2)=2（dp[1][0]=0）
  左插入(4+0)=4
  右插入(4+0)=4
  最小值=2 → dp[0][1]=2
- [1,2] "bc"：类似，dp[1][2]=2
- [2,3] "ca"：dp[2][3]=2
len=3:
- [0,2] "abc"：
  s[0]!=s[2]
  删除左: 3+dp[1][2]=3+2=5
  删除右: 3+dp[0][1]=3+2=5
  替换: 2+dp[1][1]=2+0=2
  左插入: 4+dp[0][1]=4+2=6
  右插入: 4+dp[1][2]=4+2=6
  最小值=2 → dp[0][2]=2
- [1,3] "bca"：同理，dp[1][3]=2
len=4:
- [0,3] "abca"：
  s[0]==s[3]（都是'a'），所以看内部[1,2] "bc"：dp[0][3]=dp[1][2]=2

最终答案 = 2。

复杂度分析

时间复杂度：O(n²)，因为要计算所有 O(n²) 个区间，每个区间转移是 O(1)。
空间复杂度：O(n²)，可以用滚动数组优化到 O(n)。

关键点

状态定义要清晰：dp[i][j] 是子串变成回文的最小代价。
两端相等时直接继承内部，不等时考虑所有可能操作。
注意边界条件，特别是 i>j 时代价为 0。
插入和删除在效果上可以是对称的，但代价可能不同，所以都要考虑。

合并相邻字符的最小成本问题（字符删除、替换、插入的加权版本）题目描述给定一个字符串 s 和一个字符集（例如小写字母），以及三种操作的成本：删除任意位置的一个字符，代价为 deleteCost ；替换任意位置的一个字符为另一个字符，代价为 replaceCost ；插入任意位置插入一个字符，代价为 insertCost 。目标是通过一系列操作，将字符串 s 变成一个回文串，并且总代价最小。注意，这里的替换操作只能将一个字符替换为另一个字符，不允许替换为空或从空替换。解题思路这是一个区间动态规划问题。我们考虑字符串 s 的某个子串 s[i..j] （下标从 i 到 j），定义 dp[i][j] 为将该子串变成回文串的最小代价。最终答案是 dp[0][n-1] ，其中 n 是字符串长度。状态转移思路：对于子串 s[i..j] ，我们考虑其两端的字符 s[i] 和 s[j] ：如果 s[i] == s[j] ，两端字符已经相等，那么我们可以直接考虑内部子串 s[i+1..j-1] 变成回文的代价，即 dp[i][j] = dp[i+1][j-1] 。如果 s[i] != s[j] ，我们需要通过操作使两端相等，有几种方案：删除左端，让 s[i+1..j] 变成回文，然后删除 s[i] ，代价 = dp[i+1][j] + deleteCost 。删除右端，让 s[i..j-1] 变成回文，然后删除 s[j] ，代价 = dp[i][j-1] + deleteCost 。替换左端为 s[j] ，使两端相等，然后处理内部 s[i+1..j-1] ，代价 = dp[i+1][j-1] + replaceCost 。替换右端为 s[i] ，同理代价 = dp[i+1][j-1] + replaceCost （注意替换左右端代价相同，因为 replaceCost 是固定的）。插入一个字符在左端，让它与 s[j] 相等，这样原来的 s[i..j] 就变成 s[i..j] 加上新字符，但新字符与 s[j] 配对，相当于处理 s[i..j-1] 变成回文，然后插入一个字符，代价 = dp[i][j-1] + insertCost 。插入一个字符在右端，同理代价 = dp[i+1][j] + insertCost 。实际上，由于对称性，我们可以简化：删除左端与插入右端效果类似，但代价可能不同（deleteCost vs insertCost）。替换左端与替换右端代价相同。因此，我们取这些方案的最小值。边界条件：当 i == j 时，子串长度为 1，它已经是回文，代价为 0。当 i > j 时，空串，代价为 0。计算顺序：由于 dp[i][j] 依赖于 dp[i+1][j] 、 dp[i][j-1] 、 dp[i+1][j-1] ，即依赖于更短的区间，我们可以按区间长度从小到大计算。详细步骤初始化一个二维数组 dp[n][n] ，所有值设为 0。先处理长度为 1 的区间： dp[i][i] = 0 。对于区间长度 len 从 2 到 n：对于每个起点 i，计算终点 j = i + len - 1。如果 s[i] == s[j] ：如果 len == 2 ，则 dp[i][j] = 0 （两个相同字符已经是回文）；否则 dp[i][j] = dp[i+1][j-1] 。如果 s[i] != s[j] ：方案1：删除左端 -> dp[i+1][j] + deleteCost 方案2：删除右端 -> dp[i][j-1] + deleteCost 方案3：替换左端或右端 -> dp[i+1][j-1] + replaceCost 方案4：在左端插入与 s[ j] 相同的字符 -> dp[i][j-1] + insertCost 方案5：在右端插入与 s[ i] 相同的字符 -> dp[i+1][j] + insertCost 取上述五种方案的最小值赋给 dp[i][j] 。最终 dp[0][n-1] 即为答案。示例说明假设 s = "abca" , deleteCost = 3 , replaceCost = 2 , insertCost = 4 。 n = 4 len=1: 全 0 len=2: [ 0,1 ] "ab"：不等删除左(3+dp[ 1][ 1 ]=3) = 3 删除右(3+0)=3 替换(2+dp[ 1][ 0]=2)=2（dp[ 1][ 0 ]=0）左插入(4+0)=4 右插入(4+0)=4 最小值=2 → dp[ 0][ 1 ]=2 [ 1,2] "bc"：类似，dp[ 1][ 2 ]=2 [ 2,3] "ca"：dp[ 2][ 3 ]=2 len=3: [ 0,2 ] "abc"： s[ 0]!=s[ 2 ] 删除左: 3+dp[ 1][ 2 ]=3+2=5 删除右: 3+dp[ 0][ 1 ]=3+2=5 替换: 2+dp[ 1][ 1 ]=2+0=2 左插入: 4+dp[ 0][ 1 ]=4+2=6 右插入: 4+dp[ 1][ 2 ]=4+2=6 最小值=2 → dp[ 0][ 2 ]=2 [ 1,3] "bca"：同理，dp[ 1][ 3 ]=2 len=4: [ 0,3 ] "abca"： s[ 0]==s[ 3]（都是'a'），所以看内部[ 1,2] "bc"：dp[ 0][ 3]=dp[ 1][ 2 ]=2 最终答案 = 2。复杂度分析时间复杂度：O(n²)，因为要计算所有 O(n²) 个区间，每个区间转移是 O(1)。空间复杂度：O(n²)，可以用滚动数组优化到 O(n)。关键点状态定义要清晰： dp[i][j] 是子串变成回文的最小代价。两端相等时直接继承内部，不等时考虑所有可能操作。注意边界条件，特别是 i>j 时代价为 0。插入和删除在效果上可以是对称的，但代价可能不同，所以都要考虑。