合并字符串的最小成本问题

题目描述
给定一个字符串s和一个成本数组cost，其中cost[i]表示将字符s[i]与其相邻字符合并的成本。合并操作定义为：选择两个相邻字符，将它们合并成一个新字符，新字符可以是原两个字符中的任意一个，合并的成本为cost[i]（即合并位置的成本）。求将整个字符串合并成单个字符的最小总成本。

例如，对于字符串"abc"和成本数组[1, 2, 3]，有多种合并方式：

• 先合并"ab"为"a"（成本1），再合并"ac"为"a"（成本3），总成本4
• 先合并"ab"为"b"（成本1），再合并"bc"为"b"（成本3），总成本4
• 先合并"bc"为"b"（成本2），再合并"ab"为"a"（成本1），总成本3
• 先合并"bc"为"c"（成本2），再合并"ac"为"a"（成本1），总成本3
  最小成本为3。

解题过程

步骤1：理解问题本质
这个问题要求我们将一个字符串通过相邻合并操作最终变成一个字符，每次合并的成本是合并位置对应的成本值。我们需要找到合并顺序使得总成本最小。

关键观察：

• 无论合并顺序如何，最终每个原始字符都会参与到合并中
• 合并的成本只与合并的位置有关，与合并后选择的字符无关
• 这实际上是一个区间划分问题，可以用区间DP解决

步骤2：定义DP状态
定义dp[i][j]表示将子串s[i...j]合并成单个字符所需的最小成本。

步骤3：状态转移方程
对于区间[i, j]，我们需要考虑最后一次合并的位置。假设最后一次合并发生在位置k（i ≤ k < j），即我们先合并[i, k]和[k+1, j]两个区间，然后再将这两个结果合并。

状态转移方程：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost[k])，其中k从i到j-1

解释：

• dp[i][k]：合并左半区间[i, k]的最小成本
• dp[k+1][j]：合并右半区间[k+1, j]的最小成本
• cost[k]：最后一次合并的成本（合并位置k的成本）

步骤4：初始化
对于长度为1的区间（即单个字符），不需要合并，成本为0：
dp[i][i] = 0，对于所有i

步骤5：计算顺序
按照区间长度从小到大计算：

1. 先计算所有长度为2的区间
2. 再计算所有长度为3的区间
3. 依此类推，直到计算整个字符串[0, n-1]

步骤6：详细示例
以s = "abc"，cost = [1, 2, 3]为例：

初始化：
dp[0][0] = 0, dp[1][1] = 0, dp[2][2] = 0

长度为2的区间：

• [0,1]：dp[0][1] = dp[0][0] + dp[1][1] + cost[0] = 0 + 0 + 1 = 1
• [1,2]：dp[1][2] = dp[1][1] + dp[2][2] + cost[1] = 0 + 0 + 2 = 2

长度为3的区间[0,2]：

• k=0：dp[0][0] + dp[1][2] + cost[0] = 0 + 2 + 1 = 3
• k=1：dp[0][1] + dp[2][2] + cost[1] = 1 + 0 + 2 = 3
  取最小值：dp[0][2] = min(3, 3) = 3

步骤7：算法实现

def min_merge_cost(s, cost):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 按区间长度从小到大计算
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            # 尝试所有可能的最后一次合并位置
            for k in range(i, j):
                current_cost = dp[i][k] + dp[k+1][j] + cost[k]
                dp[i][j] = min(dp[i][j], current_cost)
    
    return dp[0][n-1]

步骤8：复杂度分析

• 时间复杂度：O(n³)，需要三层循环
• 空间复杂度：O(n²)，用于存储DP表

这个解法通过系统地考虑所有可能的合并顺序，保证了找到全局最优解。