合并字符串的最小成本问题（字符插入与删除） 问题描述： 给定一个字符串s，你可以进行两种操作： 插入一个字符，成本为insertCost 删除一个字符，成本为deleteCost 你的目标是通过最少的操作成本，使得字符串变成回文串。求最小成本。 解题过程： 让我们通过一个具体例子来理解：s = "abac"，insertCost = 1，deleteCost = 1 步骤1：定义状态 我们定义dp[ i][ j]表示将子串s[ i...j ]变成回文串的最小成本。 步骤2：状态转移方程 对于任意区间[ i, j ]，我们考虑以下几种情况： 情况1：如果i == j（单个字符） 单个字符本身就是回文，成本为0： dp[ i][ j ] = 0 情况2：如果i + 1 == j（两个字符） 如果s[ i] == s[ j ]，成本为0 如果s[ i] != s[ j ]，成本为min(insertCost, deleteCost) 情况3：一般情况（j - i >= 2） 如果s[ i] == s[ j ]：两端的字符相同，不需要额外操作 dp[ i][ j] = dp[ i+1][ j-1 ] 如果s[ i] != s[ j ]：两端的字符不同，我们需要选择成本最小的操作 选择1：删除s[ i]，成本 = deleteCost + dp[ i+1][ j ] 选择2：在j后面插入s[ i]，成本 = insertCost + dp[ i+1][ j ] 选择3：删除s[ j]，成本 = deleteCost + dp[ i][ j-1 ] 选择4：在i前面插入s[ j]，成本 = insertCost + dp[ i][ j-1 ] 由于选择1和2效果相同（都是让s[ i ]与某个字符匹配），选择3和4效果相同，所以： dp[ i][ j] = min(deleteCost + dp[ i+1][ j], insertCost + dp[ i][ j-1 ]) 步骤3：计算顺序 我们需要按照区间长度从小到大的顺序计算： 长度为1的子串 长度为2的子串 长度为3的子串 ... n. 长度为n的整个字符串 步骤4：实例演示 对于s = "abac"，insertCost = 1，deleteCost = 1 初始化： dp[ 0][ 0] = 0, dp[ 1][ 1] = 0, dp[ 2][ 2] = 0, dp[ 3][ 3 ] = 0 长度为2： dp[ 0][ 1]：s[ 0]='a'≠s[ 1]='b'，min(1+dp[ 1][ 1], 1+dp[ 0][ 0 ]) = min(1+0, 1+0) = 1 dp[ 1][ 2]：s[ 1]='b'≠s[ 2]='a'，min(1+dp[ 2][ 2], 1+dp[ 1][ 1 ]) = min(1+0, 1+0) = 1 dp[ 2][ 3]：s[ 2]='a'≠s[ 3]='c'，min(1+dp[ 3][ 3], 1+dp[ 2][ 2 ]) = min(1+0, 1+0) = 1 长度为3： dp[ 0][ 2]：s[ 0]='a'=s[ 2]='a'，dp[ 0][ 2] = dp[ 1][ 1 ] = 0 dp[ 1][ 3]：s[ 1]='b'≠s[ 3]='c'，min(1+dp[ 2][ 3], 1+dp[ 1][ 2 ]) = min(1+1, 1+1) = 2 长度为4： dp[ 0][ 3]：s[ 0]='a'≠s[ 3 ]='c' 选择1：删除s[ 0]，成本 = 1 + dp[ 1][ 3 ] = 1 + 2 = 3 选择2：删除s[ 3]，成本 = 1 + dp[ 0][ 2 ] = 1 + 0 = 1 最小成本为1 最终结果：dp[ 0][ 3 ] = 1 步骤5：算法复杂度 时间复杂度：O(n²) 空间复杂度：O(n²) 这个算法可以有效地找到将任意字符串转换为回文串的最小成本，通过动态规划避免了重复计算，保证了最优解。