括号匹配的最大得分问题 题目描述： 给定一个由 '(' 和 ')' 组成的字符串 s，以及一个得分规则：每个匹配的括号对 "()" 得 1 分。你需要计算这个字符串中所有合法括号子序列的最高得分。注意：子序列不要求连续，但必须保持原始顺序。 解题过程： 问题分析： 我们需要找到字符串 s 中一个子序列，这个子序列是合法的括号序列，并且得分最高 每个匹配的括号对得 1 分，所以得分就是匹配的括号对数量 这是一个区间动态规划问题，因为我们需要考虑字符串的不同区间 状态定义： 定义 dp[ i][ j] 表示子串 s[ i...j ] 中合法括号子序列的最高得分 我们的目标是求 dp[ 0][ n-1 ]，其中 n 是字符串长度 状态转移方程： 我们需要考虑几种情况： 情况A：如果 s[ i] 和 s[ j] 匹配（即 s[ i]='(' 且 s[ j ]=')'） 我们可以选择匹配这对括号，得分 = 1 + dp[ i+1][ j-1 ] 或者不匹配这对括号，得分 = max(dp[ i+1][ j], dp[ i][ j-1 ]) 取最大值：dp[ i][ j] = max(1 + dp[ i+1][ j-1], dp[ i+1][ j], dp[ i][ j-1 ]) 情况B：如果 s[ i] 和 s[ j ] 不匹配 dp[ i][ j] = max(dp[ i+1][ j], dp[ i][ j-1 ]) 但是，还有一种重要情况需要考虑：区间内可能存在多个独立的括号对，我们需要找到最优的分割点。 更完整的状态转移： 对于区间 [ i, j ]，我们可以： 不考虑两端的字符：dp[ i][ j] = dp[ i+1][ j-1 ] 考虑用 s[ i ] 与区间内的某个位置 k 匹配（如果匹配） 更通用的做法是：dp[ i][ j] = max(dp[ i+1][ j], dp[ i][ j-1], dp[ i+1][ j-1] + (s[ i]和s[ j ]匹配 ? 2 : 0)) 但更更好的方法是考虑分割点： dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j]) 对于所有 i ≤ k < j 完整算法步骤： 初始化：dp[ i][ i ] = 0（单个字符无法形成匹配） 对于区间长度 len 从 2 到 n： 对于起始位置 i 从 0 到 n-len： j = i + len - 1 初始化 dp[ i][ j] = max(dp[ i+1][ j], dp[ i][ j-1 ]) 如果 s[ i]='(' 且 s[ j ]=')'： dp[ i][ j] = max(dp[ i][ j], dp[ i+1][ j-1 ] + 1) 对于分割点 k 从 i 到 j-1： dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j ]) 边界情况处理： 空字符串：得分为 0 所有字符都相同（全是 '(' 或全是 ')'）：得分为 0 时间复杂度：O(n³)，空间复杂度：O(n²) 示例演示： 对于字符串 s = "()()"： 区间 [ 0,3 ]：可以匹配位置0和1，位置2和3，总得分2 或者匹配位置0和3，位置1和2，总得分也是2 这个算法能正确处理所有情况，找到最优的括号匹配方案。