区间动态规划例题：布尔括号化问题 题目描述 给定一个布尔表达式，由符号 T （真）和 F （假）以及运算符 & （与）、 | （或）、 ^ （异或）组成。表达式以符号和运算符交替的形式出现，例如 T | F & T ^ F 。要求计算该表达式有多少种括号化方式，使得最终结果为 True （真）。 输入示例： s = "T|F&T^F" 输出示例：返回能使表达式为 True 的括号化方式数量。 解题思路 问题分析 ：表达式中的运算符优先级相同，但括号可以改变运算顺序。不同括号化方式会导致不同结果。 区间DP定义 ：设 dp[i][j][0] 表示子表达式 s[i:j] （包含端点）得到 False 的方式数， dp[i][j][1] 表示得到 True 的方式数。 状态转移 ：遍历区间内的每个运算符作为最后执行的运算符，根据其左右子表达式的真假组合数，更新当前区间的真假数。 初始化 ：单个符号（长度为1的子表达式）的真假值直接由符号本身决定。 最终目标 ：求整个表达式 s[0:n-1] 的 dp[0][n-1][1] 。 逐步推导 以 s = "T|F&T^F" 为例（长度为 5，符号索引为 0,2,4，运算符索引为 1,3）： 初始化单个符号 ： 对于 s[0]='T' ： dp[0][0][1]=1 , dp[0][0][0]=0 对于 s[2]='F' ： dp[2][2][1]=0 , dp[2][2][0]=1 类似初始化所有单个符号区间。 处理长度为3的区间 （如 "T|F" ）： 区间 [0,2] ，运算符 | 在索引1： 左子表达式 [0,0] ： (T=1, F=0) 右子表达式 [2,2] ： (T=0, F=1) | 运算：真值组合为 (T|T, T|F, F|T) 为真，仅 F|F 为假。 真数： 左真*右真 + 左真*右假 + 左假*右真 = 1*0 + 1*1 + 0*0 = 1 假数： 左假*右假 = 0*1 = 0 但注意：实际需累加所有划分方式，此处仅一种划分（单个运算符）。 处理更长区间 （如 "T|F&T" ）： 区间 [0,4] ，可能以 | 或 & 为最后运算符： 若以 | （索引1）划分：左 [0,0] ，右 [2,4] 需先计算右区间 "F&T" 的真假数（类似步骤2）。 若以 & （索引3）划分：左 [0,2] ，右 [4,4] 需先计算左区间 "T|F" 的真假数。 按运算符真值表组合左右结果，累加到当前区间。 最终计算 ： 自底向上填充 dp 表，区间长度从1到n（步长为2）。 结果即为 dp[0][n-1][1] 。 关键点 运算符真值表决定组合方式（如 & 仅左右真时为真）。 需遍历区间内所有可能的最后运算符位置。 时间复杂度 O(n³)，空间复杂度 O(n²)。