布尔括号化问题 题目描述 给定一个布尔表达式，由符号 'T' （真）、 'F' （假）以及运算符 '&' （与）、 '|' （或）、 '^' （异或）组成。你的目标是通过在符号间添加括号的方式，计算出有多少种括号化方案可以使整个表达式的结果为 true 。 例如，对于表达式 "T^F&T" ： 一种括号化方式： (T^(F&T)) ，结果为 T^(F&T) = T^F = T （真） 另一种括号化方式： ((T^F)&T) ，结果为 (T^F)&T = T&T = T （真） 因此，有两种方案使其为真。 解题思路 这是一个典型的区间动态规划问题。我们需要计算在表达式子区间 [i, j] 上，通过不同括号化方式能得到 true 或 false 的结果数量。 定义状态 ： 我们定义两个DP表： dpT[i][j] ：表示子表达式 expr[i...j] 能计算出 true 的方案数。 dpF[i][j] ：表示子表达式 expr[i...j] 能计算出 false 的方案数。 状态转移 ： 基础情况 ：当区间长度为1（即 i == j ）时，如果字符是 'T' ，那么 dpT[i][j] = 1 ， dpF[i][j] = 0 ；如果字符是 'F' ，那么 dpT[i][j] = 0 ， dpF[i][j] = 1 。 一般情况 ：当区间长度大于1时（即 i < j ），我们需要考虑在区间内所有可能的运算符位置进行分割。运算符位于奇数索引上（假设表达式字符串中，操作数在偶数索引，运算符在奇数索引）。对于区间 [i, j] ，我们遍历所有可能的分割点 k （ k 从 i+1 到 j-1 ，步长为2，因为 k 是运算符的位置）。 将表达式分割成左区间 [i, k-1] 和右区间 [k+1, j] ，运算符是 expr[k] 。 根据运算符的类型，组合左右区间的结果： 运算符 '&' （与）：结果为真，当且仅当左右都为真。 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]) 运算符 '|' （或）：结果为真，当左右至少一个为真。 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]) 运算符 '^' （异或）：结果为真，当左右结果不同。 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]) 初始化与计算顺序 ： 初始化所有 dpT[i][j] 和 dpF[i][j] 为0。 我们按照区间长度 len 从小到大进行遍历（从1到整个表达式长度n）。 对于每个起始点 i ，计算终点 j = i + len - 1 。 如果 len 为1，直接设置基础情况。 如果 len 为大于1的奇数（因为有效的表达式长度必须是奇数：一个操作数，然后每增加一个运算符和一个操作数，长度增加2），则进行状态转移。 最终结果 ： 整个表达式 expr[0...n-1] 能计算出 true 的方案数就是 dpT[0][n-1] 。 总结 通过区间动态规划，我们将复杂表达式分解为更小的子表达式，逐步计算每个子区间能得到真或假的方案数，最终合并得到整个表达式的解。这种方法避免了暴力枚举所有括号方案的高复杂度，通过动态规划高效地解决了问题。