区间动态规划例题：布尔括号化问题（统计真值表达式为真的方法数） 题目描述 给定一个布尔表达式，由以下字符组成： 符号：'T'（真）或 'F'（假） 运算符：'&'（与）、'|'（或）、'^'（异或） 表达式中的符号和运算符交替出现，形成一个有效的布尔表达式。例如："T|F&T^F"。 你的目标是：通过在不同位置添加括号来改变表达式的求值顺序，统计有多少种括号化方案能使整个表达式的最终结果为 'T'（真）。 解题过程 问题分析 这是一个典型的区间划分问题。每个运算符都可以作为最后一步计算的运算符，将表达式分成左右两个子表达式。 我们需要知道每个子表达式在多少种括号化方案下能得到真（T）或假（F）的结果。 因此，我们需要一个动态规划状态来记录区间内表达式结果为 T 和 F 的方案数。 定义状态 设 dp[i][j][0] 表示从第 i 个字符到第 j 个字符组成的子表达式，计算结果为 F 的方案数。 设 dp[i][j][1] 表示从第 i 个字符到第 j 个字符组成的子表达式，计算结果为 T 的方案数。 注意：i 和 j 必须是相同类型的字符（都是符号或都是运算符），且 i 和 j 的奇偶性相同。实际上，符号位于偶数索引（从0开始），运算符位于奇数索引。 状态转移 基础情况：当区间长度为1（即 i == j）时，如果字符是 'T'，则 dp[i][j][1] = 1 ， dp[i][j][0] = 0 ；如果字符是 'F'，则 dp[i][j][1] = 0 ， dp[i][j][0] = 1 。 当区间长度大于1时，我们需要枚举区间内的每个运算符作为最后一步计算的运算符。假设在位置 k（k 为奇数，且 i < k < j）的运算符将区间 [ i, j] 分成左区间 [ i, k-1] 和右区间 [ k+1, j ]。 根据运算符的类型，组合左右子表达式的结果： 运算符 '&'（与）：左右都为真时结果为真。 真方案数： leftTrue * rightTrue 假方案数： leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse 运算符 '|'（或）：左右至少一个为真时结果为真。 真方案数： leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue 假方案数： leftFalse * rightFalse 运算符 '^'（异或）：左右结果不同时为真。 真方案数： leftTrue * rightFalse + leftFalse * rightTrue 假方案数： leftTrue * rightTrue + leftFalse * rightFalse 将 k 取遍所有可能的运算符位置，累加这些方案数到 dp[i][j][0] 和 dp[i][j][1] 。 计算顺序 按区间长度从小到大进行计算。因为长区间的结果依赖于更短区间的结果。 最终结果 整个表达式对应区间 [ 0, n-1] 的 dp[0][n-1][1] ，即结果为 T 的方案数。 示例 以表达式 "T|F&T" 为例： 符号索引：0(T), 2(F), 4(T) 运算符索引：1(|), 3(&) 计算过程： 初始化长度为1的区间： dp[0][0][1]=1, [0]=0 ; dp[2][2][1]=0, [0]=1 ; dp[4][4][1]=1, [0]=0 。 计算长度为3的区间（如 [ 0,2 ]：T|F）： 运算符 k=1：| 左区间 [ 0,0]：T(1,0)，右区间 [ 2,2 ]：F(0,1) 真方案：1 1 + 1 1 + 0* 1 = 2？等等，重新计算： 真方案：leftTrue rightTrue + leftTrue rightFalse + leftFalse rightTrue = 1 0 + 1 1 + 0 0 = 1 假方案：leftFalse rightFalse = 0 1 = 0 所以 dp[0][2][1]=1, [0]=0 （实际上 T|F 为真，方案数1种） 类似计算其他区间，最终得到整个表达式的方案数。 通过这种循序渐进的区间动态规划方法，我们可以系统地统计出所有能使表达式为真的括号化方案数。