布尔括号化问题（统计真值表达式为真的方法数） 题目描述 给定一个布尔表达式，由符号 T （真）、 F （假）以及运算符 & （与）、 | （或）、 ^ （异或）组成。表达式中的符号和运算符交替出现，例如 T|F&T^F 。要求计算该表达式有多少种括号化方式，使得整个表达式的结果为 True 。注意，括号化必须保证运算符的优先级不变，仅通过添加括号改变运算顺序。 解题过程 问题分析 表达式形式为：操作数 T / F 与运算符交替出现，长度为奇数。 目标：通过添加括号改变结合顺序，统计所有能得到 True 的方案数。 关键：括号化本质是划分运算顺序，适合用区间动态规划枚举所有划分点。 状态定义 定义 dp[i][j][0] 和 dp[i][j][1] ： dp[i][j][0] 表示子表达式 s[i:j] （包含两端）通过括号化得到 False 的方案数。 dp[i][j][1] 表示得到 True 的方案数。 区间长度必须为奇数（因操作数与运算符交替）。初始时， i 和 j 均为偶数索引（从0开始），对应操作数的位置。 状态转移 遍历区间 [i, j] 内的每个运算符位置 k （ k 为奇数，表示运算符），将表达式分为左右两部分： [i, k-1] 和 [k+1, j] 。 根据运算符类型，组合左右子表达式的真值方案数： 运算符 & ：结果为真当且仅当左右均为真。 真值方案 += leftTrue * rightTrue 运算符 | ：结果为真当左右至少一个为真。 真值方案 += leftTrue * rightTotal + leftTotal * rightTrue - leftTrue * rightTrue （其中 leftTotal = leftTrue + leftFalse ，右同） 运算符 ^ ：结果为真当左右真值不同。 真值方案 += leftTrue * rightFalse + leftFalse * rightTrue 同理计算假值方案数（可根据真值方案和总方案数推导，或直接类似计算）。 初始化 单字符区间：若 s[i] 是 T ，则 dp[i][i][1] = 1 ， dp[i][i][0] = 0 ；若为 F ，则相反。 计算顺序 按区间长度从小到大遍历（步长为2，因每次增加一个运算符和一个操作数）。 结果输出 最终结果为 dp[0][n-1][1] ，其中 n 为表达式长度。 示例说明 表达式： T|F&T 长度 n=5，索引 0~4（0:T, 1:|, 2:F, 3:&, 4:T）。 初始化： dp[0][0][1]=1, [0][0][0]=0 ； dp[2][2][1]=0, [2][2][0]=1 ； dp[4][4][1]=1, [4][4][0]=0 。 区间长度3：计算 [0,2] 和 [2,4] 。 [0,2] ：运算符 | 在索引1，左 [0,0] 、右 [2,2] 。 真值方案 = 左真×右总 + 左总×右真 - 左真×右真 = 1×1 + 1×0 - 1×0 = 1。 假值方案 = 左总×右总 - 真值方案 = 1×1 - 1 = 0。 同理计算 [2,4] （运算符 & ）：真值=0×1=0，假值=1×1 - 0=1。 区间长度5： [0,4] ，遍历运算符位置1和3。 运算符 | 在索引1：左 [0,0] ，右 [2,4] 。 真值 = 左真×右总 + 左总×右真 - 左真×右真 = 1×1 + 1×0 - 1×0 = 1。 运算符 & 在索引3：左 [0,2] ，右 [4,4] 。 真值 = 左真×右真 = 1×1 = 1。 总真值方案 = 1 + 1 = 2。 最终结果为2，即两种括号化方式： (T|F)&T 和 T|(F&T) 。