最终 `dp[i][j]` 取所有可能分割中的最大值。

区间动态规划例题：括号匹配的最大得分问题 题目描述 给定一个由括号字符 '(' 和 ')' 组成的字符串 s，以及一个得分规则：每对匹配的括号得 1 分。请计算该字符串中 连续子串 的最大括号匹配得分。例如，字符串 "(()())" 的得分为 3，因为有三对匹配的括号；而字符串 "())" 的得分为 1。要求设计一个算法，求出任意给定括号字符串的连续子串的最大得分。 解题思路 本题采用区间动态规划求解。定义 dp[i][j] 表示子串 s[i:j+1] （即从索引 i 到 j 的闭区间）内的最大括号匹配得分。目标是计算 dp[0][n-1] ，其中 n 是字符串长度。 步骤分析 初始化 对于任意区间 [i, j] ，如果区间长度小于 2（即 j-i+1 < 2），则无法形成匹配括号对，得分为 0。 初始化 dp 数组所有值为 0。 区间划分与状态转移 对于每个区间 [i, j] ，考虑两种可能情况： 情况1 ：子串的首尾字符 s[i] 和 s[j] 匹配（即 s[i] == '(' 且 s[j] == ')' ）。此时，区间内的得分至少为内部子区间 [i+1, j-1] 的得分加上当前匹配的 1 分： \[ \text{score} = dp[ i+1][ j-1 ] + 1 \] 情况2 ：将区间 [i, j] 在中间某个位置 k 切开（i ≤ k < j），分成两个子区间 [i, k] 和 [k+1, j] 。总得分为两个子区间得分之和： \[ \text{score} = dp[ i][ k] + dp[ k+1][ j ] \] 最终 dp[i][j] 取所有可能分割中的最大值。 动态规划递推 按区间长度从小到大计算： 外层循环遍历区间长度 len（从 2 到 n）。 内层循环遍历区间起点 i，计算终点 j = i + len - 1。 对于每个区间 [i, j] ，先检查首尾匹配情况更新得分，再遍历所有分割点 k 更新最大值。 示例演示 以 s = "(()())" 为例（n=6）： 区间长度 len=2： [0,1] 为 "(("，不匹配； [1,2] 为 "()"，匹配，得 1 分； [2,3] 为 "(("，不匹配； [3,4] 为 "()"，得 1 分； [4,5] 为 "))"，不匹配。 逐步合并后，最终 dp[0][5] 通过组合子区间得分得到 3。 关键点总结 区间 DP 通过枚举区间长度和起点，逐步合并子问题解。 首尾匹配时直接加分，避免遗漏嵌套括号结构（如 "((()))"）。 分割点枚举确保覆盖并列括号结构（如 "()()"）。 时间复杂度 O(n³)，空间复杂度 O(n²)。