括号匹配的最大得分问题（带权值版本） 题目描述： 给定一个由 '(' 和 ')' 组成的字符串 s，以及一个得分数组 score，其中 score[ i ] 表示第 i 个字符的权值得分。我们需要找出一个合法的括号子序列（不一定连续），使得这个子序列中所有字符的权值之和最大。合法的括号序列定义为：空串是合法的；如果 A 和 B 是合法的，那么 AB 也是合法的；如果 A 是合法的，那么 (A) 也是合法的。 解题过程： 定义状态：设 dp[ i][ j] 表示在子串 s[ i:j+1 ]（即从索引 i 到 j 的闭区间）中，能获得的最大得分。注意，这里我们考虑的是不要求连续的子序列。 状态转移： 情况1：不考虑字符 i。那么最大得分就是 dp[ i+1][ j ]。 情况2：如果 s[ i] 是 '('，我们尝试为它匹配一个在位置 k (i < k <= j) 的 ')'，使得 s[ k ] 是 ')'。这样，我们可以将区间分成三部分： 内部区间 [ i+1, k-1]：这是一个合法的括号序列，得分是 dp[ i+1][ k-1 ]。 匹配的括号对 (i, k)：得分是 score[ i] + score[ k ]。 外部区间 [ k+1, j]：得分是 dp[ k+1][ j ]。 总得分是这三部分的和。我们需要遍历所有可能的 k，取最大值。 此外，区间 [ i, j] 可能由两个合法的括号序列拼接而成，即存在一个分割点 m (i <= m < j)，使得总得分 = dp[ i][ m] + dp[ m+1][ j ]。我们也需要遍历所有可能的 m，取最大值。 初始化：对于长度为0的区间（即 i > j），dp[ i][ j] = 0。对于长度为1的区间，由于单个字符无法形成合法的括号对（除非是空，但空序列得分0），所以 dp[ i][ i ] = 0。 计算顺序：由于 dp[ i][ j ] 依赖于更短的区间（即区间长度更小），所以我们按区间长度 len 从小到大进行计算，从 len=2 开始（因为至少需要两个字符才能形成一对括号）。 最终答案：整个字符串 s[ 0:n-1] 的最大得分就是 dp[ 0][ n-1 ]。 举例说明： 假设 s = "()()", score = [ 1, 2, 3, 4 ]。 区间长度2： [ 0,1]: s[ 0]='(', s[ 1]=')'，匹配，得分=1+2=3。dp[ 0][ 1 ]=3。 [ 1,2]: s[ 1]=')', s[ 2]='('，无法匹配，dp[ 1][ 2 ]=0。 [ 2,3]: s[ 2]='(', s[ 3]=')'，匹配，得分=3+4=7。dp[ 2][ 3 ]=7。 区间长度4：[ 0,3 ]： 情况1：不考虑s[ 0]，得分=dp[ 1][ 3]。需要计算dp[ 1][ 3]：区间[ 1,3]=")("，内部无法形成合法序列，但可以分割为[ 1,2]和[ 3,3]（但dp[ 3][ 3]=0），所以dp[ 1][ 3 ]=0。 情况2：s[ 0 ]='('，尝试匹配k=1,3。 k=1：内部[ 1,0]无效（得分0），匹配得分=1+2=3，外部[ 2,3 ]得分=7，总=10。 k=3：内部[ 1,2]=")("，dp[ 1][ 2 ]=0，匹配得分=1+4=5，外部无，总=5。 最大值10。 情况3：分割点m=1：dp[ 0][ 1]+dp[ 2][ 3 ]=3+7=10。 所以dp[ 0][ 3 ]=max(0, 10, 10)=10。 最终最大得分是10，对应的子序列是取整个字符串"()()"。