布尔括号化问题

题目描述
给定一个布尔表达式，由符号 T（true）、F（false）以及运算符 &（与）、|（或）、^（异或）组成。表达式中的符号和运算符交替出现，例如 T|F&T^F。我们的目标是通过添加括号来改变表达式的计算顺序，使得表达式最终计算结果为 true 的方法数是多少？
例如，表达式 T|T&F^T 可以通过不同的加括号方式得到不同的结果，需要统计使其结果为 true 的括号化方案数量。

解题思路
这个问题是区间动态规划的经典应用。我们需要定义一个二维 DP 表，其中 dp[i][j][0] 表示从第 i 个符号到第 j 个符号的子表达式计算结果为 false 的方案数，dp[i][j][1] 表示结果为 true 的方案数。符号和运算符交替出现，因此区间长度必须为奇数。

步骤分解

1. 定义状态
   设表达式字符串为 s，长度为 n（n 为奇数）。
   定义 dp[i][j][0] 和 dp[i][j][1]，其中 i 和 j 是符号的索引（即 i 和 j 为偶数，且 0 <= i <= j < n）。

2. 初始化
   对于单个符号（区间长度为1）：

   • 如果 s[i] == 'T'，则 dp[i][i][1] = 1，dp[i][i][0] = 0。
   • 如果 s[i] == 'F'，则 dp[i][i][1] = 0，dp[i][i][0] = 1。

3. 状态转移
   对于区间 [i, j]，我们枚举中间运算符的位置 k（k 为奇数，i < k < j），将表达式分割为左右两个子区间 [i, k-1] 和 [k+1, j]。
   根据运算符 s[k] 的类型，组合左右子区间的结果：

   • 与运算 (&)：
     • 结果为 true：左右均为 true → dp[i][k-1][1] * dp[k+1][j][1
     • 结果为 false：其他情况（左真右假、左假右真、左假右假）之和。
   • 或运算 (|)：
     • 结果为 true：至少一边为 true（左真右假、左假右真、左真右真）之和。
     • 结果为 false：左右均为 false。
   • 异或运算 (^)：
     • 结果为 true：左右结果不同（左真右假 + 左假右真）。
     • 结果为 false：左右结果相同（左真右真 + 左假右假）。

   具体公式：

   for k in range(i+1, j, 2):  # k 为运算符位置
       left_true = dp[i][k-1][1], left_false = dp[i][k-1][0]
       right_true = dp[k+1][j][1], right_false = dp[k+1][j][0]
       if s[k] == '&':
           dp[i][j][1] += left_true * right_true
           dp[i][j][0] += left_true * right_false + left_false * right_true + left_false * right_false
       elif s[k] == '|':
           dp[i][j][1] += left_true * right_false + left_false * right_true + left_true * right_true
           dp[i][j][0] += left_false * right_false
       elif s[k] == '^':
           dp[i][j][1] += left_true * right_false + left_false * right_true
           dp[i][j][0] += left_true * right_true + left_false * right_false
   

4. 计算顺序
   按区间长度从小到大计算（长度 len = 3, 5, ..., n），确保子区间结果已计算。

5. 结果
   最终答案为 dp[0][n-1][1]，即整个表达式结果为 true 的方案数。

举例说明
表达式："T|F&T"（长度 5，索引 0~4）

1. 初始化单个符号：
   • dp[0][0][1]=1, [0]=0（T）
   • dp[2][2][1]=0, [0]=1（F）
   • dp[4][4][1]=1, [0]=0（T）
2. 计算长度 3 的区间 [0,2]（T|F）：
   • 运算符 | 在索引 1：
     • true 方案：左真右假(11) + 左假右真(00) + 左真右真(1*0) = 1
     • false 方案：左假右假(0*1) = 0
   • 区间 [2,4]（F&T）类似计算（略）。
3. 计算整个区间 [0,4]（运算符 | 在索引 1 和 3）：
   • 以索引 1 分割：左区间 [0,0]（T），右区间 [2,4]（F&T 的结果为 false？需先算）
   • 逐步合并后得到最终方案数。

通过系统化计算，可避免重复枚举所有括号组合，时间复杂度为 O(n³)。