括号匹配的最大得分问题

题目描述
给定一个由括号字符 '(' 和 ')' 组成的字符串 s，以及一个得分数组 score，其中 score[i] 表示第 i 对匹配括号的得分。字符串 s 中恰好有 n 对匹配的括号，你需要计算所有可能的括号匹配方式中，得分之和的最大值。

解题过程

1. 问题分析
这是一个区间动态规划问题。我们需要在给定的括号序列中找到一种匹配方式，使得所有匹配括号对的得分之和最大。由于括号匹配具有递归结构（一个有效的括号序列可以分解为更小的有效序列），这很适合用区间DP来解决。

2. 状态定义
定义 dp[i][j] 表示子串 s[i...j] 中所有匹配括号对的最大得分和。

3. 状态转移
考虑子串 s[i...j]：

• 如果 s[i] 和 s[j] 是一对匹配的括号，那么：
  dp[i][j] = dp[i+1][j-1] + score[k] （其中k是这对括号的得分索引）
• 但是，字符串可能包含多个独立的有效括号序列，所以我们需要枚举所有可能的分割点：
  dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])，对于所有 i ≤ k < j

4. 具体步骤
让我们通过一个例子来详细说明：
s = "()(())"，score = [1, 2, 3]

步骤1：初始化
dp[0][5] 表示整个字符串的最大得分

步骤2：基础情况

• 单个字符：dp[i][i] = 0（无法形成匹配）
• 长度为2的子串：如果是"()"，得分为对应的score

步骤3：计算过程

• 计算长度为2的子串：
  dp[0][1] = 1（"()"）
  dp[2][3] = 2（"()"）
  dp[4][5] = 3（"()"）

• 计算长度为4的子串：
  dp[2][5]：考虑"(() )"
  情况1：s[2]和s[5]匹配：dp[3][4] + score = 0 + ?
  情况2：在位置3分割：dp[2][3] + dp[4][5] = 2 + 3 = 5
  情况3：在位置4分割：dp[2][4] + dp[5][5] = 0 + 0 = 0
  最大值为5

• 计算整个字符串：
  dp[0][5]：考虑"()(())"
  情况1：s[0]和s[5]不匹配
  情况2：在位置1分割：dp[0][1] + dp[2][5] = 1 + 5 = 6
  情况3：在位置2分割：dp[0][2] + dp[3][5] = 0 + 0 = 0
  情况4：在位置3分割：dp[0][3] + dp[4][5] = 0 + 3 = 3
  情况5：在位置4分割：dp[0][4] + dp[5][5] = 0 + 0 = 0
  最大值为6

5. 算法实现

def maxBracketScore(s, score):
    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
            
            # 情况1：在中间分割
            for k in range(i, j):
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])
            
            # 情况2：首尾匹配
            if s[i] == '(' and s[j] == ')':
                # 需要确定这对括号对应的score索引
                pair_count = 0
                # 这里需要根据实际情况确定score索引
                # 假设我们有一个方法来确定
                current_score = determine_score(i, j, score)
                dp[i][j] = max(dp[i][j], dp[i+1][j-1] + current_score)
    
    return dp[0][n-1]

6. 复杂度分析

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

7. 关键点

• 括号匹配的递归结构是解题核心
• 需要考虑所有可能的分割方式
• 需要正确处理score数组与括号对的对应关系
• 边界情况处理要仔细

这个解法能够有效地找到括号匹配的最大得分，适用于各种括号序列和得分配置。