合并相邻字符的最小成本问题（字符替换与删除的进阶版） 题目描述： 给定一个字符串s和一个成本数组cost，其中cost[ i]表示删除或替换字符s[ i ]的成本。我们可以执行两种操作： 删除任意位置的字符，成本为cost[ i ] 替换任意位置的字符为另一个字符，成本为cost[ i ] 目标是通过这些操作使得字符串变成回文串，求最小总成本。 解题过程： 问题分析： 我们需要将字符串转换为回文串 可以删除字符或替换字符 每个操作都有对应的成本 目标是找到成本最小的操作序列 定义状态： 设dp[ i][ j]表示将子串s[ i...j ]变成回文串的最小成本。 状态转移方程： 考虑子串s[ i...j ]的边界情况： 情况1：如果s[ i] == s[ j ] 当i == j时：dp[ i][ j ] = 0（单个字符已经是回文） 当i + 1 == j时：dp[ i][ j ] = 0（两个相同字符已经是回文） 否则：dp[ i][ j] = dp[ i+1][ j-1 ]（两端字符相同，不需要操作） 情况2：如果s[ i] != s[ j ] 我们有三种选择： a) 删除s[ i]，成本为cost[ i] + dp[ i+1][ j ] b) 删除s[ j]，成本为cost[ j] + dp[ i][ j-1 ] c) 替换s[ i]或s[ j ]使得它们相等： 替换s[ i]为s[ j]，成本为cost[ i] + dp[ i+1][ j-1 ] 替换s[ j]为s[ i]，成本为cost[ j] + dp[ i+1][ j-1 ] 因此：dp[ i][ j ] = min( cost[ i] + dp[ i+1][ j], // 删除s[ i ] cost[ j] + dp[ i][ j-1], // 删除s[ j ] cost[ i] + dp[ i+1][ j-1], // 替换s[ i]为s[ j ] cost[ j] + dp[ i+1][ j-1] // 替换s[ j]为s[ i ] ) 边界条件： 当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 ]，我们需要按子串长度从小到大计算。 示例演示： 假设s = "abc", cost = [ 1,2,3 ] 计算dp[ 0][ 2 ]（子串"abc"）： s[ 0]='a' ≠ s[ 2 ]='c' 选项1：删除'a'，成本=1 + dp[ 1][ 2 ] = 1 + min(删除'b',删除'c',...) = 1 + 2 = 3 选项2：删除'c'，成本=3 + dp[ 0][ 1 ] = 3 + min(删除'a',删除'b',...) = 3 + 1 = 4 选项3：替换'a'为'c'，成本=1 + dp[ 1][ 1 ] = 1 + 0 = 1 选项4：替换'c'为'a'，成本=3 + dp[ 1][ 1 ] = 3 + 0 = 3 最小成本为1 算法实现： 从长度为1的子串开始，逐步计算到整个字符串，最终dp[ 0][ n-1 ]就是答案。 这个解法的时间复杂度是O(n²)，空间复杂度是O(n²)，可以优化到O(n)的空间复杂度。