括号插入的最小成本问题（相邻括号匹配代价） 题目描述 给定一个由字符 '(' 和 ')' 组成的字符串 s，你可以在任意位置插入任意数量的括号（'(' 或 ')'），每次插入的成本为 1。你的目标是插入最少的括号，使得整个字符串变成有效的括号序列。有效括号序列的定义是：空字符串是有效的；如果 A 和 B 是有效的，那么 AB 也是有效的；如果 A 是有效的，那么 (A) 也是有效的。请计算最小插入成本。 解题过程 问题分析 这是一个典型的区间动态规划问题。我们需要将整个字符串划分为子区间，逐步计算每个子区间变成有效括号序列的最小成本。关键在于如何定义状态和状态转移方程。 状态定义 设 dp[ i][ j] 表示将子串 s[ i:j+1]（即从索引 i 到 j 的子串）变成有效括号序列的最小插入成本。我们的目标是计算 dp[ 0][ n-1 ]，其中 n 是字符串 s 的长度。 基础情况 当子串长度为 0（即 i > j）时，空字符串本身就是有效的，成本为 0：dp[ i][ j ] = 0（若 i > j）。 当子串长度为 1 时，单个字符无法形成有效括号，需要插入一个匹配的括号，成本为 1：dp[ i][ i ] = 1。 状态转移方程 对于子串 s[ i:j+1 ]，我们考虑两种可能的情况： 情况1 ：s[ i] 和 s[ j] 可以匹配（即 s[ i] 是 '(' 且 s[ j] 是 ')'）。如果它们匹配，那么我们可以先处理内部子串 s[ i+1:j]（即从 i+1 到 j-1 的部分），成本为 dp[ i+1][ j-1]。但注意：s[ i] 和 s[ j] 本身已经存在，不需要额外插入成本来匹配它们，因此 dp[ i][ j] 可能等于 dp[ i+1][ j-1 ]。 情况2 ：无论 s[ i] 和 s[ j] 是否匹配，我们都可以将子串分割成两部分：s[ i:k+1] 和 s[ k+1:j+1]（其中 i ≤ k < j）。总成本是两部分成本之和：dp[ i][ k] + dp[ k+1][ j ]。我们需要遍历所有可能的分割点 k，取最小值。 综合以上情况，状态转移方程为： dp[ i][ j ] = min( dp[ i+1][ j-1] 如果 s[ i] 和 s[ j ] 匹配, min(dp[ i][ k] + dp[ k+1][ j ]) 对于所有 k 从 i 到 j-1 ) 计算顺序 由于 dp[ i][ j] 依赖于更短的子区间（如 dp[ i+1][ j-1] 和 dp[ i][ k]、dp[ k+1][ j ]），我们需要按子串长度从小到大计算。具体顺序： 首先处理长度为 1 的子串（基础情况）。 然后依次处理长度为 2, 3, ..., n 的子串。 示例演算 以 s = "())" 为例（n=3）： 初始化：所有长度为 1 的子串成本为 1（dp[ 0][ 0]=1, dp[ 1][ 1]=1, dp[ 2][ 2 ]=1）。 长度 2 的子串： s[ 0:2] = "()"：s[ 0]='(' 和 s[ 1]=')' 匹配，dp[ 0][ 1] = dp[ 1][ 0 ]（空串成本为 0） = 0。 s[ 1:3] = "))"：s[ 1]=')' 和 s[ 2]=')' 不匹配，需分割：min(dp[ 1][ 1]+dp[ 2][ 2]=1+1=2) → dp[ 1][ 2 ]=2。 长度 3 的子串 s[ 0:3 ] = "())"： 检查首尾：s[ 0]='(' 和 s[ 2]=')' 匹配，但内部子串 s[ 1:2] = ")" 成本为 dp[ 1][ 1 ]=1，所以候选值1为 1。 分割点 k=0：dp[ 0][ 0]+dp[ 1][ 2]=1+2=3；k=1：dp[ 0][ 1]+dp[ 2][ 2 ]=0+1=1。 最小值是 min(1, 3, 1) = 1。 最终结果：dp[ 0][ 2 ] = 1。 算法实现要点 时间复杂度 O(n³)，空间复杂度 O(n²)。 注意边界条件（如空串处理）。 实际代码中，可通过循环长度 len 从 1 到 n，然后遍历起始点 i，计算 j = i + len - 1。 通过以上步骤，我们可以系统地计算出任意字符串的最小插入成本，确保括号序列有效。