最小成本构造回文串问题（字符替换与删除） 题目描述： 给定一个字符串s，你可以进行两种操作： 删除任意位置的字符，成本为del_ cost 替换任意位置的字符为另一个字符，成本为rep_ cost 请计算将字符串s转换为回文串的最小总成本。 解题过程： 问题分析 我们需要将任意字符串转换为回文串，可以删除或替换字符。回文串的特点是正读反读都一样，即对于任意位置i，s[ i] = s[ n-i-1 ]。 定义状态 令dp[ i][ j]表示将子串s[ i...j]转换为回文串的最小成本，其中0 ≤ i ≤ j < n。 状态转移方程 考虑子串s[ i...j]的边界字符s[ i]和s[ j ]： 情况1：如果s[ i] == s[ j ] 两个字符已经相等，不需要额外操作 dp[ i][ j] = dp[ i+1][ j-1 ] （当j-i ≥ 1） 当j-i ≤ 1时，dp[ i][ j ] = 0（已经是回文） 情况2：如果s[ i] != s[ j ] 我们有三种选择： 删除s[ i]，成本为del_ cost + dp[ i+1][ j ] 删除s[ j]，成本为del_ cost + dp[ i][ j-1 ] 替换其中一个字符使它们相等： 替换s[ i]为s[ j]，成本为rep_ cost + dp[ i+1][ j-1 ] 替换s[ j]为s[ i]，成本为rep_ cost + dp[ i+1][ j-1 ] 因此状态转移方程为： dp[ i][ j ] = min( del_ cost + dp[ i+1][ j ], // 删除左字符 del_ cost + dp[ i][ j-1 ], // 删除右字符 rep_ cost + dp[ i+1][ j-1 ] // 替换一个字符 ) 边界条件 当i == j时，单个字符本身就是回文，dp[ i][ j ] = 0 当i > j时，空字符串是回文，dp[ i][ j ] = 0 计算顺序 由于dp[ i][ j]依赖于dp[ i+1][ j]、dp[ i][ j-1]和dp[ i+1][ j-1 ]，我们需要按区间长度从小到大计算： 先计算长度为1的区间 然后计算长度为2的区间 依此类推，直到计算整个字符串 最终结果 最终答案为dp[ 0][ n-1 ]，其中n是字符串s的长度。 举例说明： 假设s = "abc"，del_ cost = 1，rep_ cost = 2 计算过程： dp[ 0][ 0] = 0, dp[ 1][ 1] = 0, dp[ 2][ 2 ] = 0 长度2区间： "ab": min(删除a:1+dp[ 1][ 1]=1, 删除b:1+dp[ 0][ 0]=1, 替换:2+dp[ 1][ 0 ]=2) = 1 "bc": 同理得1 长度3区间"abc"： s[ 0]='a' ≠ s[ 2 ]='c' min(删除a:1+dp[ 1][ 2]=1+1=2, 删除c:1+dp[ 0][ 1]=1+1=2, 替换:2+dp[ 1][ 1 ]=2+0=2) = 2 因此最小成本为2。