最长括号匹配子序列的最大得分问题（带权重版本）

题目描述

我们有一个由字符 '(' 和 ')' 组成的字符串 s，长度为 n。另外给出一个长度同样为 n 的整数数组 values，其中 values[i] 表示字符 s[i] 的权重。

我们定义一个括号匹配子序列为原字符串 s 的一个子序列，且这个子序列中的括号是匹配的（即它是一个有效的括号序列）。注意：子序列不要求连续，只要保持原字符串中的相对顺序即可。

目标：在所有可能的括号匹配子序列中，找到权重之和最大的那个，返回其权重总和。如果不存在匹配的括号子序列，则返回 0。

示例：

s = "()(())"
values = [1, 2, 3, 4, 5, 6]

一个可能的括号匹配子序列是选取索引 0,1,4,5 的字符，得到 "()()"，权重和为 1+2+5+6=14。
但最大得分的子序列是选取所有字符（整个字符串已经是匹配的），得到 "()(())"，权重和 = 1+2+3+4+5+6=21。

解题思路

这个问题是“最长有效括号子序列”的带权重扩展。

• 基本括号匹配子序列问题可以用区间 DP 解决：定义 dp[l][r] 表示在区间 [l, r] 内能形成的最长有效括号子序列的长度。
• 这里变成了带权值的最大得分，因此 dp[l][r] 应表示在区间 [l, r] 内能形成的括号匹配子序列的最大权重和。
• 关键点：匹配子序列不要求连续，所以可以在区间内跳过一些字符，只选择能匹配的括号对，并累加它们的权重。

状态定义

定义：

dp[l][r] = 在区间 [l, r]（闭区间）内，能得到的括号匹配子序列的最大权重和。

最终答案就是 dp[0][n-1]。

状态转移

考虑区间 [l, r]：

情况1：字符 s[l] 不参与匹配（被跳过）
那么最大得分就是 dp[l+1][r]。

情况2：字符 s[l] 参与匹配，它必须和某个位置 k（l < k ≤ r）的 s[k] 匹配，且 s[l] 是 '('，s[k] 是 ')'。
匹配后，这一对括号贡献的权重是 values[l] + values[k]。
这对括号内部的区间 [l+1, k-1] 可以独立形成一个匹配子序列，最大得分是 dp[l+1][k-1]。
这对括号外部的右侧区间 [k+1, r] 也可以独立形成一个匹配子序列，最大得分是 dp[k+1][r]。

因此，如果 s[l] 与 s[k] 匹配：

得分 = values[l] + values[k] + dp[l+1][k-1] + dp[k+1][r]

我们要枚举所有可能的 k，取最大值。

情况3：s[l] 是 ')'，它不可能作为左括号匹配，所以只能被跳过，此时回到情况1。

情况4：区间长度 ≤ 0 时，dp[l][r] = 0。

综合起来：

dp[l][r] = max(
    dp[l+1][r],  # 跳过 s[l]
    如果 s[l] == '('：
        max_{k: l<k≤r, s[k]==')'} (values[l] + values[k] + dp[l+1][k-1] + dp[k+1][r])
)

注意：即使 s[l] 是 '('，也可以选择跳过它，所以总是有跳过的情况。

计算顺序

因为区间长度小的 dp 值要先求，所以按区间长度从小到大计算。

举例推导

s = "()", values = [3, 5]，n=2。

• 初始化 dp[0][1] 为 0。
• 区间长度 2：l=0, r=1，s[0]=='('，s[1]==')'，可以匹配。
  跳过情况：dp[1][1] = 0。
  匹配情况：k=1，得分 = 3+5+dp[1][0]+dp[2][1]。其中 dp[1][0] 区间无效为 0，dp[2][1] 区间无效为 0，总得分 8。
  取最大值 8。
  最终 dp[0][1]=8。

算法步骤

1. 初始化 dp[n][n] 为 0，dp[i][i] = 0（单个字符无法匹配）。
2. 按长度 len 从 2 到 n 遍历：
   • 遍历左端点 l 从 0 到 n-len，r = l+len-1。
   • 先令 dp[l][r] = dp[l+1][r]（跳过 s[l]）。
   • 如果 s[l] == '('：
     • 遍历 k 从 l+1 到 r：
       • 如果 s[k] == ')'：
         • 内部区间得分 = dp[l+1][k-1]（如果 l+1 > k-1 则为 0）。
         • 外部区间得分 = dp[k+1][r]（如果 k+1 > r 则为 0）。
         • 总得分 = values[l] + values[k] + 内部得分 + 外部得分。
         • 更新 dp[l][r] = max(dp[l][r], 总得分)。
3. 返回 dp[0][n-1]。

时间复杂度

状态数 O(n²)，每个状态内部要枚举 k（最多 O(n)），总时间复杂度 O(n³)。
可以用前缀和或预处理优化到 O(n²)，但基础版本 O(n³) 可接受（n 一般在 200 以内）。

核心要点

• 这是区间 DP 经典问题，匹配不要求连续，所以枚举匹配对时中间和两侧可以独立计算。
• 跳过左端字符的情况必须考虑，因为可能跳过左括号去匹配更优的右括号。
• 如果题目要求连续的子串匹配，则用不同的 DP 定义（通常一维或二维表示以 i 结尾的最长有效括号子串）；这里是子序列，所以是区间 DP。