最长括号匹配子序列问题（带权值版本） 题目描述 给定一个只包含'('和')'的字符串s，以及每个字符的权值数组w。我们需要找到s的一个子序列，这个子序列是有效的括号序列，并且具有最大的权值和。有效的括号序列定义为：空字符串是有效的；如果A是有效的，那么(A)也是有效的；如果A和B都是有效的，那么AB也是有效的。 解题思路 这个问题需要找到权值最大的有效括号子序列。我们可以使用区间动态规划来解决，定义dp[ i][ j]表示在子串s[ i:j+1 ]中，最大权值的有效括号子序列的权值和。 详细解题步骤 状态定义 定义dp[ i][ j]为子串s[ i:j+1 ]（包含i和j）中，最大权值的有效括号子序列的权值和。 初始化 对于所有长度为0或1的区间： 当i > j时，区间为空，dp[ i][ j ] = 0 当i = j时，单个字符无法形成有效括号，dp[ i][ j ] = 0 状态转移方程 考虑区间[ i, j ]的最大权值有效括号子序列，有几种情况： 情况1：不考虑端点字符 dp[ i][ j] = max(dp[ i][ j], dp[ i+1][ j ]) // 不考虑左端点 dp[ i][ j] = max(dp[ i][ j], dp[ i][ j-1 ]) // 不考虑右端点 情况2：端点字符匹配 如果s[ i] == '('且s[ j ] == ')'，那么可以考虑将这两个字符作为最外层的括号： dp[ i][ j] = max(dp[ i][ j], dp[ i+1][ j-1] + w[ i] + w[ j ]) 情况3：分割区间 对于所有k ∈ [ i, j-1 ]，将区间分割为两部分： dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j ]) 遍历顺序 按照区间长度从小到大进行遍历： 先遍历长度为2的区间 然后长度递增，直到整个字符串的长度 最终结果 整个字符串的最大权值有效括号子序列的权值和就是dp[ 0][ n-1 ]，其中n是字符串长度。 示例演示 假设s = "()()"，w = [ 1, 2, 3, 4 ] 长度为2的区间： [ 0,1]: s[ 0]='(', s[ 1]=')'匹配，dp[ 0][ 1 ] = max(0, 0+1+2) = 3 [ 1,2]: s[ 1]=')', s[ 2]='('不匹配，dp[ 1][ 2] = max(dp[ 1][ 1], dp[ 2][ 2 ]) = 0 [ 2,3]: s[ 2]='(', s[ 3]=')'匹配，dp[ 2][ 3 ] = max(0, 0+3+4) = 7 长度为3的区间： [ 0,2]: 端点不匹配，考虑分割：max(dp[ 0][ 1]+dp[ 2][ 2], dp[ 0][ 0]+dp[ 1][ 2 ]) = max(3+0, 0+0) = 3 [ 1,3]: 端点不匹配，考虑分割：max(dp[ 1][ 2]+dp[ 3][ 3], dp[ 1][ 1]+dp[ 2][ 3 ]) = max(0+0, 0+7) = 7 长度为4的区间[ 0,3 ]： 端点匹配：s[ 0]='(', s[ 3]=')'，dp[ 0][ 3] = dp[ 1][ 2 ] + 1 + 4 = 0 + 1 + 4 = 5 不考虑端点：max(dp[ 1][ 3], dp[ 0][ 2 ]) = max(7, 3) = 7 分割：max(dp[ 0][ 1]+dp[ 2][ 3 ]) = 3 + 7 = 10 最终dp[ 0][ 3 ] = max(5, 7, 10) = 10 算法复杂度 时间复杂度：O(n³)，需要三重循环 空间复杂度：O(n²)，需要二维dp数组 这个算法通过系统地考虑所有可能的括号匹配方式和区间分割方式，确保了找到权值最大的有效括号子序列。