区间动态规划例题：最长括号匹配子序列问题（带权值版本） 题目描述： 给定一个由 '(' 和 ')' 组成的字符串 s，以及一个权值数组 w，其中 w[ i ] 表示第 i 个字符的权值。请找出最长的有效括号子序列，并计算其权值和。有效括号子序列定义为：空字符串是有效的；如果 A 是有效的，那么 (A) 也是有效的；如果 A 和 B 是有效的，那么 AB 也是有效的。 解题过程： 问题分析 我们需要在字符串 s 中找到一个子序列（不一定连续），这个子序列是有效的括号序列，并且我们希望这个子序列尽可能长。当有多个最长有效括号子序列时，我们需要找出权值和最大的那个。 状态定义 定义 dp[ i][ j] 表示在子串 s[ i:j+1 ] 中，最长有效括号子序列的长度和对应的最大权值和。我们可以用一个元组 (length, weight) 来表示。 状态转移方程 考虑区间 [ i, j ] 的最优解： 情况1：不包含字符 s[ i ] dp[ i][ j] = dp[ i+1][ j ] 情况2：包含字符 s[ i]，且 s[ i ] 是 '(' 我们需要在区间 [ i+1, j ] 中找到一个 ')' 与它匹配 对于所有 k ∈ [ i+1, j]，如果 s[ k ] == ')'，那么： 候选解 = (dp[ i+1][ k-1].length + dp[ k+1][ j ].length + 2, dp[ i+1][ k-1].weight + dp[ k+1][ j].weight + w[ i] + w[ k ]) 情况3：直接合并两个子区间 对于所有 k ∈ [ i, j-1 ]： 候选解 = (dp[ i][ k].length + dp[ k+1][ j].length, dp[ i][ k].weight + dp[ k+1][ j ].weight) 初始化 对于长度为1的区间，dp[ i][ i ] = (0, 0)（单个字符无法形成有效括号对） 对于空区间，dp[ i][ i-1 ] = (0, 0) 计算顺序 按照区间长度从小到大计算： 先计算长度为2的区间 然后计算长度为3的区间 依此类推，直到计算整个字符串 最终结果 dp[ 0][ n-1 ] 就是整个字符串的最长有效括号子序列的长度和最大权值和。 举例说明： 假设 s = "()()", w = [ 1, 2, 3, 4 ] 最长有效括号子序列可以是 "()()"（长度4，权值和1+2+3+4=10） 或者 "(())"（长度4，权值和1+4+2+3=10） 通过这个动态规划过程，我们可以在 O(n³) 的时间复杂度内解决问题，其中 n 是字符串长度。