布尔括号化问题（带权值版本） 题目描述： 给定一个布尔表达式，由符号 'T'（true）、'F'（false）和运算符 '&'（与）、'|'（或）、'^'（异或）组成。表达式中的符号和运算符交替出现，例如 "T|F&T^F"。现在，你可以在任意位置添加括号来改变运算顺序，但不能改变符号和运算符的原始顺序。 问题要求：计算通过不同的括号化方式，使得整个表达式最终结果为 True 的方法数。 解题过程： 步骤1：理解问题结构 表达式由操作数和运算符交替组成 我们需要考虑所有可能的括号化方式 这是一个区间划分问题，适合用区间DP解决 步骤2：定义DP状态 我们定义两个DP数组： dpT[ i][ j ]：表示子表达式从第i个符号到第j个符号，计算结果为True的方法数 dpF[ i][ j ]：表示子表达式从第i个符号到第j个符号，计算结果为False的方法数 步骤3：确定状态转移 对于区间[ i,j ]，我们考虑在哪个运算符位置进行划分： 如果区间长度为1（即单个操作数）： 如果是'T'：dpT[ i][ i] = 1, dpF[ i][ i ] = 0 如果是'F'：dpT[ i][ i] = 0, dpF[ i][ i ] = 1 如果区间长度大于1： 我们在每个运算符位置k（i < k < j）进行划分，将表达式分为左右两部分 根据运算符的类型，计算组合结果： 对于运算符 '&'（与）： True = 左True & 右True dpT[ i][ j] += dpT[ i][ k-1] * dpT[ k+1][ j ] dpF[ i][ j] += (dpT[ i][ k-1] * dpF[ k+1][ j]) + (dpF[ i][ k-1] * dpT[ k+1][ j]) + (dpF[ i][ k-1] * dpF[ k+1][ j ]) 对于运算符 '|'（或）： True = 左True | 右True dpT[ i][ j] += (dpT[ i][ k-1] * dpT[ k+1][ j]) + (dpT[ i][ k-1] * dpF[ k+1][ j]) + (dpF[ i][ k-1] * dpT[ k+1][ j ]) dpF[ i][ j] += dpF[ i][ k-1] * dpF[ k+1][ j ] 对于运算符 '^'（异或）： True = 左True ^ 右False 或 左False ^ 右True dpT[ i][ j] += (dpT[ i][ k-1] * dpF[ k+1][ j]) + (dpF[ i][ k-1] * dpT[ k+1][ j ]) dpF[ i][ j] += (dpT[ i][ k-1] * dpT[ k+1][ j]) + (dpF[ i][ k-1] * dpF[ k+1][ j ]) 步骤4：实现细节 按区间长度从小到大计算 外层循环：区间长度len从1到n（步长为2，因为符号和运算符交替） 内层循环：区间起始位置i 最内层循环：划分位置k（运算符位置） 步骤5：示例演示 以表达式 "T|F&T" 为例： 符号序列：T(0) |(1) F(2) &(3) T(4) 计算过程： 初始化长度为1的区间： dpT[ 0][ 0]=1, dpF[ 0][ 0 ]=0 dpT[ 2][ 2]=0, dpF[ 2][ 2 ]=1 dpT[ 4][ 4]=1, dpF[ 4][ 4 ]=0 长度为3的区间[ 0,2 ]（T|F）： 在位置1划分（运算符|）： dpT[ 0][ 2] += dpT[ 0][ 0] dpT[ 2][ 2] + dpT[ 0][ 0] dpF[ 2][ 2] + dpF[ 0][ 0] dpT[ 2][ 2 ] = 1 0 + 1 1 + 0 0 = 1 dpF[ 0][ 2] += dpF[ 0][ 0] dpF[ 2][ 2] = 0 1 = 0 区间[ 2,4 ]（F&T）同理计算... 最终计算整个区间[ 0,4 ]... 最终结果存储在dpT[ 0][ n-1 ]中，表示整个表达式结果为True的方法数。 这个算法的时间复杂度是O(n³)，空间复杂度是O(n²)，能高效解决中等规模的布尔表达式括号化问题。