区间动态规划例题：布尔表达式求值问题（统计不同括号化方式的数量） 题目描述 给定一个布尔表达式字符串，其中只包含字符 'T' （真）、 'F' （假）以及运算符 '&' （与）、 '|' （或）、 '^' （异或）。要求计算通过不同的括号化方式，使得整个表达式的结果为 True 的方案数。例如，表达式 "T|F&T" 可以通过添加括号得到不同的计算顺序，求结果为 True 的括号化方式数量。 解题过程 步骤1：问题分析 表达式的形式为：操作数（ T / F ）和运算符交替出现，例如 T | F & T 对应序列 [T, |, F, &, T] 。 不同括号化方式对应不同的运算顺序，例如 (T|F)&T 和 T|(F&T) 会得到不同的结果。 目标：统计所有括号化方式中，使表达式结果为 True 的数量。 步骤2：定义状态 使用区间动态规划，定义 dp[i][j][0] 和 dp[i][j][1] ： dp[i][j][0] 表示子表达式 s[i:j+1] 计算结果为 False 的方案数。 dp[i][j][1] 表示子表达式 s[i:j+1] 计算结果为 True 的方案数。 注意：表达式长度必须为奇数，且索引 i 到 j 的子串中，操作数位于偶数位（0-based），运算符位于奇数位。 步骤3：状态转移 基础情况：当子串长度为1（即 i == j ）时，直接判断操作数： 若 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 。 一般情况（ i < j ）：遍历所有可能的运算符位置 k （ k 为奇数位，表示运算符），将表达式分为左右两部分： 左子区间： [i, k-1] ，右子区间： [k+1, j] 。 根据运算符 s[k] 的类型，组合左右子区间的结果： 运算符 '&' ：结果为真当且仅当左右均为真。 dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1] dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0] 运算符 '|' ：结果为真当且仅当至少一侧为真。 dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][1] dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] 运算符 '^' ：结果为真当且仅当左右真假性不同。 dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1] dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + dp[i][k-1][1] * dp[k+1][j][1] 步骤4：计算顺序 按区间长度从小到大计算（长度 len 从 1 到 n ，每次增加2，因为表达式长度必须为奇数）。 对于每个长度，枚举区间起点 i ，计算终点 j = i + len - 1 ，再枚举中间运算符位置 k 。 步骤5：结果提取 最终结果为 dp[0][n-1][1] ，即整个表达式计算结果为 True 的方案数。 举例说明 表达式 "T|F&T" 的序列为 [T, |, F, &, T] ，长度为5。 基础： dp[0][0][1]=1 , dp[2][2][0]=1 , dp[4][4][1]=1 。 计算长度3的子串： 子串 "T|F" ：运算符 | 在索引1，组合左右结果得到 dp[0][2][1] = 1 （真）。 子串 "F&T" ：运算符 & 在索引3，组合得到 dp[2][4][1] = 0 （假）。 计算全长：运算符 | 在索引1或 & 在索引3，分别计算后累加，最终得到结果为 True 的方案数。 通过以上步骤，即可系统性地求解布尔表达式的括号化方案数问题。