区间动态规划例题：布尔括号化问题（统计真值表达式为真的方法数）

字数 1432 2025-11-04 08:32:42

区间动态规划例题：布尔括号化问题（统计真值表达式为真的方法数）

题目描述
给定一个布尔表达式，由以下字符组成：

符号 'T'（表示 True）
符号 'F'（表示 False）
运算符 '&'（AND）、'|'（OR）、'^'（XOR）

表达式以符号和运算符交替的形式出现，例如 "T|F&T^F"。要求计算该表达式通过不同括号化方式能得到 True 的总方法数。例如，表达式 "T|T&F" 可以括号化为 (T|(T&F)) 或 ((T|T)&F)，两种方式的结果可能不同。

解题思路

问题分析：表达式长度为奇数，偶数索引位置（0-based）为符号（T/F），奇数索引位置为运算符。通过添加括号改变运算顺序，本质是划分表达式的子区间，递归计算左右两部分的结果组合。
区间DP定义：
- 设 dp[i][j][0] 表示子表达式 expr[i:j]（包含端点）能生成 False 的方法数。
- dp[i][j][1] 表示生成 True 的方法数。
- 区间长度必须为奇数（即 (j-i) % 2 == 0）。
状态转移：
- 遍历区间 [i, j] 中的每个运算符位置 k（k 为奇数索引），将表达式分为左区间 [i, k-1] 和右区间 [k+1, j]。
- 根据运算符类型，组合左右区间的真值结果：
  - &：True 需左右均为 True；False 可为其他三种组合。
  - |：False 需左右均为 False；True 可为其他三种组合。
  - ^：True 需左右真值不同；False 需左右真值相同。
- 累加所有划分方式的结果：
```
dp[i][j][真值] += left_cnt * right_cnt  
```
初始化：
- 单符号区间（i == j）：若为 T，则 dp[i][j][1] = 1，dp[i][j][0] = 0；若为 F，则相反。
最终目标：求 dp[0][n-1][1]，其中 n 为表达式长度。

详细步骤

输入处理：表达式如 "T|F&T"，长度为 5。
初始化DP表：
- 单符号区间：
  - dp[0][0][1] = 1（因 expr[0]='T'），dp[0][0][0] = 0。
  - dp[2][2][0] = 1（因 expr[2]='F'），dp[2][2][1] = 0。
  - 类似处理其他单符号。
区间长度从 3 开始遍历（最小运算单元如 T|F）：
- 例：区间 [0,2]，运算符在 k=1（|）：
  - 左区间 [0,0]：(T=1, F=0)；右区间 [2,2]：(T=0, F=1)。
  - 按 | 规则：
    - True：左真右假(11) + 左假右真(00) + 左真右真(1*0) = 1。
    - False：左假右假(0*1) = 0。
  - 更新 dp[0][2][1] = 1，dp[0][2][0] = 0。
扩展至全长：
- 对 [0,4]，遍历 k=1,3：
  - k=1（|）：左区间 [0,0]，右区间 [2,4]（需先计算 dp[2][4]）。
  - 类似组合真值并累加。
输出：dp[0][n-1][1] 即为所求。

关键点

运算符仅在奇数索引位置，划分时需确保左右子区间长度为奇数。
真值组合需严格按逻辑运算规则计算。
时间复杂度 O(n³)，空间复杂度 O(n²)。

区间动态规划例题：布尔括号化问题（统计真值表达式为真的方法数）题目描述给定一个布尔表达式，由以下字符组成：符号 'T' （表示 True）符号 'F' （表示 False）运算符 '&' （AND）、 '|' （OR）、 '^' （XOR）表达式以符号和运算符交替的形式出现，例如 "T|F&T^F" 。要求计算该表达式通过不同括号化方式能得到 True 的总方法数。例如，表达式 "T|T&F" 可以括号化为 (T|(T&F)) 或 ((T|T)&F) ，两种方式的结果可能不同。解题思路问题分析：表达式长度为奇数，偶数索引位置（0-based）为符号（ T / F ），奇数索引位置为运算符。通过添加括号改变运算顺序，本质是划分表达式的子区间，递归计算左右两部分的结果组合。区间DP定义：设 dp[i][j][0] 表示子表达式 expr[i:j] （包含端点）能生成 False 的方法数。 dp[i][j][1] 表示生成 True 的方法数。区间长度必须为奇数（即 (j-i) % 2 == 0 ）。状态转移：遍历区间 [i, j] 中的每个运算符位置 k （ k 为奇数索引），将表达式分为左区间 [i, k-1] 和右区间 [k+1, j] 。根据运算符类型，组合左右区间的真值结果： & ： True 需左右均为 True； False 可为其他三种组合。 | ： False 需左右均为 False； True 可为其他三种组合。 ^ ： True 需左右真值不同； False 需左右真值相同。累加所有划分方式的结果：初始化：单符号区间（ i == j ）：若为 T ，则 dp[i][j][1] = 1 ， dp[i][j][0] = 0 ；若为 F ，则相反。最终目标：求 dp[0][n-1][1] ，其中 n 为表达式长度。详细步骤输入处理：表达式如 "T|F&T" ，长度为 5。初始化DP表：单符号区间： dp[0][0][1] = 1 （因 expr[0]='T' ）， dp[0][0][0] = 0 。 dp[2][2][0] = 1 （因 expr[2]='F' ）， dp[2][2][1] = 0 。类似处理其他单符号。区间长度从 3 开始遍历（最小运算单元如 T|F ）：例：区间 [0,2] ，运算符在 k=1 （ | ）：左区间 [0,0] ： (T=1, F=0) ；右区间 [2,2] ： (T=0, F=1) 。按 | 规则： True ：左真右假(1 1) + 左假右真(0 0) + 左真右真(1* 0) = 1。 False ：左假右假(0* 1) = 0。更新 dp[0][2][1] = 1 ， dp[0][2][0] = 0 。扩展至全长：对 [0,4] ，遍历 k=1,3 ： k=1 （ | ）：左区间 [0,0] ，右区间 [2,4] （需先计算 dp[2][4] ）。类似组合真值并累加。输出： dp[0][n-1][1] 即为所求。关键点运算符仅在奇数索引位置，划分时需确保左右子区间长度为奇数。真值组合需严格按逻辑运算规则计算。时间复杂度 O(n³)，空间复杂度 O(n²)。