括号匹配的最大得分问题（带符号权重版本） 题目描述 给定一个由括号字符组成的字符串s，其中可能包含'('和')'。每个括号都有一个对应的权重值，这些权重值存储在一个整数数组weights中，weights的长度与s相同。我们的目标是找出一个得分最高的合法括号子序列。 合法括号序列的定义是： 空字符串是合法的 如果A是合法的，那么(A)也是合法的 如果A和B都是合法的，那么AB也是合法的 得分的计算规则是： 对于每个匹配的括号对（即一对'('和')'），它们的得分是这两个括号权重值的乘积 整个子序列的得分是所有这样的匹配对的得分之和 解题思路 这个问题可以使用区间动态规划来解决。我们定义dp[ i][ j]表示子串s[ i...j ]中能够获得的最大得分。 状态转移分析 对于任意区间[ i, j ]，我们考虑以下几种情况： 基本情况 ：如果i > j，区间为空，得分为0 区间长度小于2 ：无法形成匹配对，得分为0 一般情况 ：我们有两种选择 不将s[ i]作为匹配的左括号：dp[ i][ j] = dp[ i+1][ j ] 将s[ i]与区间内的某个')'匹配：遍历所有可能的k(i < k ≤ j)，如果s[ i]是'('且s[ k ]是')'，那么可以考虑这对匹配 详细的状态转移方程 对于区间[ i, j ]： dp[ i][ j] = max(dp[ i][ j], dp[ i+1][ j]) // 不考虑s[ i ] 如果s[ i ]是'('，遍历所有k从i+1到j： 如果s[ k ]是')'，那么这对括号可以匹配 匹配后的得分 = weights[ i] × weights[ k] + dp[ i+1][ k-1] + dp[ k+1][ j ] dp[ i][ j] = max(dp[ i][ j ], 上述得分) 算法步骤 初始化n × n的dp数组，全部设为0 按区间长度从小到大遍历（长度从2到n） 对于每个起始位置i，计算结束位置j = i + len - 1 应用状态转移方程计算dp[ i][ j ] 最终结果存储在dp[ 0][ n-1 ]中 示例演示 考虑输入：s = "()()", weights = [ 1, 2, 3, 4 ] 区间长度2： [ 0,1]: s[ 0]='(', s[ 1 ]=')' → 得分 = 1×2 = 2 [ 1,2 ]: 不匹配（以')'开头） [ 2,3]: s[ 2]='(', s[ 3 ]=')' → 得分 = 3×4 = 12 区间长度4：[ 0,3 ] 情况1：不考虑s[ 0]，得分 = dp[ 1][ 3 ] = 12 情况2：s[ 0]与s[ 1]匹配：1×2 + dp[ 2][ 3 ] = 2 + 12 = 14 情况3：s[ 0]与s[ 3]匹配：1×4 + dp[ 1][ 2] + dp[ 4][ 3 ] = 4 + 0 + 0 = 4 最大得分 = max(12, 14, 4) = 14 时间复杂度分析 需要遍历所有O(n²)个区间 对于每个区间，需要遍历所有可能的分割点，O(n) 总时间复杂度：O(n³) 空间复杂度：O(n²) 这个算法能够有效地找到带权括号序列的最大得分，通过动态规划避免了重复计算，保证了最优解的获取。