奇怪的打印机 II（颜色替换成本版本） 题目描述： 有一个奇怪的打印机，它打印时每次可以执行两种操作： 在字符串任意位置打印任意字符，成本为cost_ add 替换字符串中所有出现的某个字符为另一个字符，成本为cost_ replace 给定一个目标字符串s，求打印机打印出该字符串的最小总成本。 解题过程： 让我们循序渐进地分析这个问题： 问题分析： 这是一个区间动态规划问题，因为我们需要考虑字符串的子区间 两种操作都有成本，我们需要找到最优的操作序列 关键观察：替换操作会影响整个字符串中所有相同的字符 状态定义： 定义dp[ i][ j]表示打印出子串s[ i...j ]的最小成本 基础情况： 当i > j时，dp[ i][ j ] = 0（空字符串不需要操作） 当i = j时，dp[ i][ j] = cost_ add（单个字符直接打印） 状态转移方程： 情况1：直接打印最后一个字符 dp[ i][ j] = dp[ i][ j-1] + cost_ add 情况2：如果s[ j]在区间[ i, j-1 ]中出现过，设位置为k 我们可以考虑先打印s[ i...k]，然后通过替换操作将字符s[ k]替换为s[ j ] 这样打印s[ k+1...j-1 ]的成本可能更低 dp[ i][ j] = min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j-1] + cost_ replace) 情况3：更一般的情况，我们可以将区间分割 dp[ i][ j] = min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j])，其中i ≤ k < j 算法步骤： 初始化dp数组 按区间长度从小到大计算 对于每个区间[ i, j ]，考虑所有可能的分割点 返回dp[ 0][ n-1 ] 示例分析： 假设s = "abc"，cost_ add = 1，cost_ replace = 1 区间长度1： dp[ 0][ 0 ] = 1 ("a") dp[ 1][ 1 ] = 1 ("b") dp[ 2][ 2 ] = 1 ("c") 区间长度2： "ab"：min(dp[ 0][ 1] + 1, dp[ 0][ 0] + dp[ 1][ 1 ]) = min(1+1, 1+1) = 2 "bc"：同理为2 区间长度3： "abc"：考虑所有分割点 直接打印：dp[ 0][ 2] = dp[ 0][ 1 ] + 1 = 2 + 1 = 3 分割：min(dp[ 0][ 0]+dp[ 1][ 2], dp[ 0][ 1]+dp[ 2][ 2 ]) = min(1+2, 2+1) = 3 替换：检查是否有相同字符，这里没有 最终结果为3 时间复杂度：O(n³)，空间复杂度：O(n²) 这个解法通过考虑字符替换的可能性，在传统区间DP基础上增加了对颜色替换操作的优化处理。