区间动态规划例题：布尔表达式求值问题（统计不同括号化方式的数量） 题目描述 给定一个布尔表达式，由字符 'T' （表示 true ）、 'F' （表示 false ）以及运算符 '&' （AND）、 '|' （OR）、 '^' （XOR）组成。表达式中的符号按顺序交替出现，例如： "T|F&T^F" 。目标是计算通过不同的括号化方式，使表达式最终求值为 true 的方法数量。 示例： 输入： "T|T&F^T" 输出：使表达式为 true 的括号化方式有 4 种。 解题过程 1. 问题分析 表达式由操作数（ T / F ）和运算符（ & 、 | 、 ^ ）交替组成，长度为奇数。 通过添加括号改变运算顺序，求最终结果为 true 的方案数。 核心思路：使用区间动态规划，定义子问题 dp[i][j][0] 和 dp[i][j][1] ，分别表示子表达式 s[i:j] 求值为 false 和 true 的方法数。 2. 状态定义 设 dp[i][j][0] 表示子串 s[i:j] （包含两端）能计算出 false 的方案数。 设 dp[i][j][1] 表示子串 s[i:j] 能计算出 true 的方案数。 初始状态：长度为 1 的子串，若为 'T' ，则 dp[i][i][1] = 1 ， dp[i][i][0] = 0 ；若为 'F' ，则反之。 3. 状态转移方程 遍历每个区间 [i, j] ，仅考虑长度为奇数的区间（因为表达式合法长度必为奇数）。 在区间 [i, j] 内，遍历每个可能的分割点 k （ k 为运算符位置，即 k = i+1, i+3, ..., j-1 ）。 根据运算符类型，组合左右子区间的结果： 若 s[k] == '&' ： true 仅当左右均为 true ： dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1] false 包括其他情况： 左真右假 + 左假右真 + 左假右假 若 s[k] == '|' ： true 包括： 左真右真 + 左真右假 + 左假右真 false 仅当左右均为 false 若 s[k] == '^' ： true 当左右不同： 左真右假 + 左假右真 false 当左右相同： 左真右真 + 左假右假 4. 计算顺序 按区间长度从小到大计算： 长度 len = 1, 3, 5, ..., n 对每个区间 [i, j] ，遍历所有分割点 k （运算符位置），更新 dp[i][j][0/1] 。 5. 最终结果 答案为 dp[0][n-1][1] ，即整个表达式求值为 true 的方案数。 举例说明 以 "T|T&F^T" 为例： 初始化长度为 1 的子串： dp[0][0] = [0,1] （ T ）， dp[2][2] = [0,1] （ T ）， dp[4][4] = [1,0] （ F ）， dp[6][6] = [0,1] （ T ） 计算长度 3 的区间： [0,2] （ T|T ）：运算符 | 在位置 1， true 数 = 1*1 + 1*0 + 0*1 = 1 ， false 数 = 0*0 = 0 其他区间类似计算... 逐步合并至整个区间 [0,6] ，得到 dp[0][6][1] = 4 。 通过以上步骤，即可系统性地求出所有使表达式为 true 的括号化方案数。