布尔括号化问题（统计真值表达式为真的方法数） 题目描述 给定一个布尔表达式，由字符 'T' （真）、 'F' （假）、 '&' （与）、 '|' （或）、 '^' （异或）以及括号组成。表达式中的操作符位于两个布尔值之间，例如 "T|F&T" 。要求计算该表达式有多少种括号添加方式，使得整个表达式的计算结果为 True 。注意，输入表达式已省略括号，仅保留操作数和操作符，且操作符优先级相同（需通过括号明确运算顺序）。 示例 输入： "T|F&T" 输出： 3 解释：可能的括号添加方式包括： ((T|F)&T) → (T&T) → T (T|(F&T)) → (T|F) → T T|(F&T) 与第二种相同，但题目要求统计所有不同的括号化方案（通常按递归结构计数）。 解题思路 问题分析 ：表达式可视为操作数（ T / F ）和操作符（ & 、 | 、 ^ ）交替组成的序列。括号添加方式本质是确定操作符的运算顺序，每种顺序对应一棵二叉树（操作符为根，操作数为叶子）。 区间DP定义 ： 设 dp[i][j][0] 表示子表达式 s[i:j] （包含两端）计算结果为 False 的方案数。 dp[i][j][1] 表示计算结果为 True 的方案数。 最终目标是求 dp[0][n-1][1] ，其中 n 为表达式长度。 区间划分 ：遍历每个区间 [i, j] ，枚举区间内的每个操作符位置 k （ k 为操作符下标），将表达式分为左子表达式 [i, k-1] 和右子表达式 [k+1, j] ，根据操作符类型组合左右结果。 详细步骤 初始化 ： 对于长度为1的区间（即单个字符），若为 'T' ，则 dp[i][i][1] = 1 ， dp[i][i][0] = 0 ；若为 'F' ，则反之。 其他区间初始值为0。 区间长度遍历 ： 区间长度 len 从3开始（至少包含一个操作符和两个操作数），每次增加2（因为操作数与操作符交替）。 例如： len=3 对应 a?b （ a , b 为操作数， ? 为操作符）。 枚举区间和操作符 ： 对于每个区间 [i, j] ，遍历所有操作符位置 k （ k 从 i+1 到 j-1 ，步长为2，因为操作符位于奇数索引）。 根据操作符 s[k] 的类型，组合左区间 [i, k-1] 和右区间 [k+1, j] 的真/假方案数： 与操作 & ：结果为真需左右均为真： true_count = left_true * right_true 结果为假的情况：左假右真、左真右假、左假右假： false_count = left_true*right_false + left_false*right_true + left_false*right_false 或操作 | ：结果为假需左右均为假： false_count = left_false * right_false 结果为真：左真右假、左假右真、左真右真： true_count = left_true*right_false + left_false*right_true + left_true*right_true 异或操作 ^ ：结果为真需左右不同： true_count = left_true*right_false + left_false*right_true 结果为假需左右相同： false_count = left_true*right_true + left_false*right_false 累加方案数 ： 对每个操作符位置 k ，计算出的 true_count 和 false_count 累加到 dp[i][j][1] 和 dp[i][j][0] 。 最终结果 ：返回 dp[0][n-1][1] 。 示例推导（表达式 "T|F&T"） 表达式符号索引： 0:T, 1:|, 2:F, 3:&, 4:T 初始化单个字符： dp[0][0][1]=1, dp[0][0][0]=0 dp[2][2][1]=0, dp[2][2][0]=1 dp[4][4][1]=1, dp[4][4][0]=0 长度3的区间 [0,2] （对应 "T|F" ）： 操作符 | 在索引1： true_count = left_true*right_false + left_false*right_true + left_true*right_true = 1*1 + 0*0 + 1*0 = 1 false_count = left_false*right_false = 0*1 = 0 dp[0][2][1] = 1, dp[0][2][0] = 0 长度3的区间 [2,4] （对应 "F&T" ）： 操作符 & 在索引3： true_count = left_true*right_true = 0*1 = 0 false_count = ... = 1*1 + 0*0 + 1*0 = 1 dp[2][4][1] = 0, dp[2][4][0] = 1 长度5的区间 [0,4] （整个表达式）： 枚举操作符位置1（ | ）和3（ & ）： 操作符 | 在索引1：左区间 [0,0] ，右区间 [2,4] true_count = 1*1 + 0*0 + 1*0 = 1 （右区间为假时方案数1） false_count = 0*1 = 0 操作符 & 在索引3：左区间 [0,2] ，右区间 [4,4] true_count = 1*1 = 1 false_count = 1*0 + 0*1 + 0*0 = 0 累加： dp[0][4][1] = 1 + 1 = 2 ？但示例输出为3。 注意 ：实际需考虑左右区间的所有组合。修正： 对操作符 | 在索引1： true_count = dp[0][0][1]*dp[2][4][0] + dp[0][0][0]*dp[2][4][1] + dp[0][0][1]*dp[2][4][1] = 1*1 + 0*0 + 1*0 = 1 对操作符 & 在索引3： true_count = dp[0][2][1]*dp[4][4][1] = 1*1 = 1 遗漏情况 ：操作符优先级组合可能重复？实际上需严格按二叉树结构计数，每个操作符作为根仅一次。示例中第三种方案对应 (T|(F&T)) 和 T|(F&T) 被视为同一括号化（输入无括号时计数唯一）。但题目通常要求不同二叉树结构数，故输出3的正确计算需验证所有划分。 修正计算 （完整计数）： 操作符 | 在索引1：左 T ，右 F&T （右区间有1种方式为真： F&T 为假，但 F&T 实际为假，故右区间真方案数0？）： 右区间 [2,4] 为 F&T ，其真方案数：操作符 & 在索引3：左 F 假，右 T 真 → 真方案数=0。 因此 true_count = 1*0 + 0*1 + 1*1? 需重新核对。实际应直接套用公式： 正确计算 ： 操作符 | 在索引1： true_count = left_true*right_false + left_false*right_true + left_true*right_true = 1*1 + 0*0 + 1*0 = 1 false_count = left_false*right_false = 0*1 = 0 操作符 & 在索引3：左区间 [0,2] 为 T|F （真方案数1，假方案数0），右区间 [4,4] 为 T （真1假0）： true_count = 1*1 = 1 false_count = 1*0 + 0*1 + 0*0 = 0 总真方案数 = 1 + 1 = 2，与示例3不符。 问题 ：示例中表达式 "T|F&T" 的3种方式实为： (T|F)&T T|(F&T) T|F&T （无括号，默认左结合？） 但题目通常要求显式括号化，且结合律不影响计数。常见解法中，输出3的正确性需假设操作符优先级相同，且括号化方案按二叉树结构数（卡特兰数相关）。本例标准答案应为2种二叉树结构： 根为 | ：左 T ，右 F&T （右子树根为 & ） 根为 & ：左 T|F ，右 T 但若输入为 "T|T&F" 等会有不同结果。本题示例可能存争议，但算法逻辑正确。 总结 本题通过区间DP枚举所有括号化方式，核心是依操作符类型组合左右子区间的真/假方案数。时间复杂度O(n³)，空间复杂度O(n²)。