区间动态规划例题：合并相邻字符的最小成本问题（字符删除与合并） 题目描述： 给定一个字符串s和一个成本数组cost，其中cost[ i]表示删除字符s[ i ]的成本。你可以执行以下两种操作： 删除任意位置的字符，成本为cost[ i ] 合并两个相邻的相同字符，合并后的字符保持不变，成本为0 目标是删除所有字符，使得字符串变为空串，求最小总成本。 解题过程： 问题分析 这是一个区间动态规划问题，我们需要找到最优的操作顺序来最小化总成本。关键观察是： 合并操作成本为0，可以让我们"免费"消除相邻的相同字符 删除操作有成本，应该尽量避免 最优策略可能是先进行一些合并操作，最后再删除无法合并的字符 状态定义 定义dp[ i][ j]表示将子串s[ i...j ]完全消除所需的最小成本。 状态转移方程 考虑子串s[ i...j ]的消除方式： 情况1：直接删除第一个字符s[ i ] dp[ i][ j] = cost[ i] + dp[ i+1][ j ] 情况2：找到某个位置k (i < k ≤ j)，使得s[ i] = s[ k ] 我们可以先消除s[ i+1...k-1]，然后将s[ i]和s[ k ]合并，最后消除剩余部分 dp[ i][ j] = min(dp[ i][ j], dp[ i+1][ k-1] + dp[ k][ j ]) 边界条件 当i > j时，空子串的消除成本为0：dp[ i][ j ] = 0 当i = j时，单个字符只能删除：dp[ i][ j] = cost[ i ] 计算顺序 按照区间长度从小到大计算： 先计算长度为1的区间 再计算长度为2的区间 依此类推，直到计算整个字符串 示例演示 考虑s = "aba", cost = [ 1, 2, 1 ] 初始化： dp[ 0][ 0] = cost[ 0 ] = 1 dp[ 1][ 1] = cost[ 1 ] = 2 dp[ 2][ 2] = cost[ 2 ] = 1 其他dp[ i][ j ]初始化为较大值 计算长度为2的区间： [ 0,1]: s[ 0]≠s[ 1 ]，只能删除 dp[ 0][ 1] = min(cost[ 0]+dp[ 1][ 1], dp[ 0][ 0]+cost[ 1 ]) = min(1+2, 1+2) = 3 dp[ 1][ 2] = min(cost[ 1]+dp[ 2][ 2], dp[ 1][ 1]+cost[ 2 ]) = min(2+1, 2+1) = 3 计算长度为3的区间[ 0,2 ]： 情况1：删除s[ 0]，成本=1+dp[ 1][ 2 ]=1+3=4 情况2：s[ 0]=s[ 2 ]='a'，找到k=2 先消除[ 1,1]，成本=dp[ 1][ 1 ]=2 然后合并s[ 0]和s[ 2 ]，成本=0 总成本=2+0=2 所以dp[ 0][ 2 ]=min(4,2)=2 最终答案：dp[ 0][ 2 ] = 2 算法复杂度 时间复杂度：O(n³)，需要三重循环 空间复杂度：O(n²)，用于存储dp数组 这个问题的关键在于识别合并操作的机会，通过动态规划找到最优的合并和删除顺序来最小化总成本。