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

字数 2414 2025-11-03 18:00:43

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

题目描述
给定一个布尔表达式，由字符 'T'（真）、'F'（假）以及运算符 '&'（与）、'|'（或）、'^'（异或）组成。表达式中的符号和运算符交替出现，例如 "T|F&T^F"。要求计算有多少种括号添加方式，使得整个表达式的结果为 True。由于括号可以任意添加（但需保证运算符左右都有操作数），最终需要返回所有可能方式的总数。

解题思路

将表达式拆分为符号数组和运算符数组，例如 "T|F&T^F" 拆分为 symbols = ['T','F','T','F'] 和 operators = ['|','&','^']。
定义 dp[i][j][0] 表示子表达式 symbols[i..j] 计算结果为 False 的方法数，dp[i][j][1] 表示计算结果为 True 的方法数。
通过区间动态规划，枚举每个区间 [i, j] 内的分割点 k，根据运算符类型组合左右子区间的真值数量。

步骤详解

状态定义
设 n 为符号个数（即 symbols 的长度），dp[i][j][0] 和 dp[i][j][1] 分别表示从第 i 个符号到第 j 个符号的子表达式能计算为 False 和 True 的方法数（i, j 从 0 开始索引）。
初始化
对于长度为 1 的区间（即 i = j）：
- 若 symbols[i] = 'T'，则 dp[i][i][1] = 1，dp[i][i][0] = 0。
- 若 symbols[i] = 'F'，则 dp[i][i][1] = 0，dp[i][i][0] = 1。
状态转移
枚举区间长度 len 从 2 到 n（即子表达式的符号个数），对于每个区间 [i, j]（j = i + len - 1），枚举分割点 k（i ≤ k < j），其中 operators[k] 是 symbols[k] 和 symbols[k+1] 之间的运算符。
根据运算符类型，组合左区间 [i, k] 和右区间 [k+1, j] 的真值数量：
- 运算符 '&'（与）：
  结果为 True 仅当左右均为 True：
  True_count = left_True * right_True
  结果为 False 的情况包括：左真右假、左假右真、左假右假：
  False_count = left_True * right_False + left_False * right_True + left_False * right_False
- 运算符 '|'（或）：
  结果为 False 仅当左右均为 False：
  False_count = left_False * right_False
  结果为 True 的情况包括：左真右假、左假右真、左真右真：
  True_count = left_True * right_False + left_False * right_True + left_True * right_True
- 运算符 '^'（异或）：
  结果为 True 当左右真值不同：
  True_count = left_True * right_False + left_False * right_True
  结果为 False 当左右真值相同：
  False_count = left_True * right_True + left_False * right_False
  将当前分割点 k 产生的真值数量累加到 dp[i][j][0] 和 dp[i][j][1]。
最终结果
整个表达式的结果为 dp[0][n-1][1]，即从第一个符号到最后一个符号计算为 True 的方法数。

示例演示
以表达式 "T|F&T^F" 为例：

symbols = ['T','F','T','F']，operators = ['|','&','^']。
初始化单个符号：
dp[0][0][1]=1, dp[0][0][0]=0（符号 T）
dp[1][1][1]=0, dp[1][1][0]=1（符号 F）
dp[2][2][1]=1, dp[2][2][0]=0（符号 T）
dp[3][3][1]=0, dp[3][3][0]=1（符号 F）
计算区间 [0,1]（运算符 '|'）：
True_count = 11 + 00 + 11 = 2（左真右假、左真右真）
False_count = 01 = 1（左假右假？需核对：实际为左假右假=01=0，但左真右假等已算入真？这里应修正为：False_count = left_False right_False = 01=0，True_count=11+00+11=2？）
修正计算：
正确计算：
True = left_Trueright_False + left_Falseright_True + left_Trueright_True = 11 + 00 + 11 = 2
False = left_Falseright_False = 01 = 0
因此 dp[0][1][1]=2, dp[0][1][0]=0。
逐步计算更大区间，最终得到 dp[0][3][1] 即为答案。

复杂度分析

时间复杂度：O(n³)，需要三重循环（区间长度、起始点、分割点）。
空间复杂度：O(n²)，用于存储 dp 表。

区间动态规划例题：布尔括号化问题（统计真值表达式为真的方法数）题目描述给定一个布尔表达式，由字符 'T'（真）、'F'（假）以及运算符 '&'（与）、'|'（或）、'^'（异或）组成。表达式中的符号和运算符交替出现，例如 "T|F&T^F"。要求计算有多少种括号添加方式，使得整个表达式的结果为 True。由于括号可以任意添加（但需保证运算符左右都有操作数），最终需要返回所有可能方式的总数。解题思路将表达式拆分为符号数组和运算符数组，例如 "T|F&T^F" 拆分为 symbols = [ 'T','F','T','F'] 和 operators = [ '|','&','^' ]。定义 dp[ i][ j][ 0] 表示子表达式 symbols[ i..j] 计算结果为 False 的方法数，dp[ i][ j][ 1 ] 表示计算结果为 True 的方法数。通过区间动态规划，枚举每个区间 [ i, j ] 内的分割点 k，根据运算符类型组合左右子区间的真值数量。步骤详解状态定义设 n 为符号个数（即 symbols 的长度），dp[ i][ j][ 0] 和 dp[ i][ j][ 1 ] 分别表示从第 i 个符号到第 j 个符号的子表达式能计算为 False 和 True 的方法数（i, j 从 0 开始索引）。初始化对于长度为 1 的区间（即 i = j）：若 symbols[ i] = 'T'，则 dp[ i][ i][ 1] = 1，dp[ i][ i][ 0 ] = 0。若 symbols[ i] = 'F'，则 dp[ i][ i][ 1] = 0，dp[ i][ i][ 0 ] = 1。状态转移枚举区间长度 len 从 2 到 n（即子表达式的符号个数），对于每个区间 [ i, j]（j = i + len - 1），枚举分割点 k（i ≤ k < j），其中 operators[ k] 是 symbols[ k] 和 symbols[ k+1 ] 之间的运算符。根据运算符类型，组合左区间 [ i, k] 和右区间 [ k+1, j ] 的真值数量：运算符 '&'（与）：结果为 True 仅当左右均为 True： True_ count = left_ True * right_ True 结果为 False 的情况包括：左真右假、左假右真、左假右假： False_ count = left_ True * right_ False + left_ False * right_ True + left_ False * right_ False 运算符 '|'（或）：结果为 False 仅当左右均为 False： False_ count = left_ False * right_ False 结果为 True 的情况包括：左真右假、左假右真、左真右真： True_ count = left_ True * right_ False + left_ False * right_ True + left_ True * right_ True 运算符 '^'（异或）：结果为 True 当左右真值不同： True_ count = left_ True * right_ False + left_ False * right_ True 结果为 False 当左右真值相同： False_ count = left_ True * right_ True + left_ False * right_ False 将当前分割点 k 产生的真值数量累加到 dp[ i][ j][ 0] 和 dp[ i][ j][ 1 ]。最终结果整个表达式的结果为 dp[ 0][ n-1][ 1 ]，即从第一个符号到最后一个符号计算为 True 的方法数。示例演示以表达式 "T|F&T^F" 为例： symbols = [ 'T','F','T','F']，operators = [ '|','&','^' ]。初始化单个符号： dp[ 0][ 0][ 1]=1, dp[ 0][ 0][ 0 ]=0（符号 T） dp[ 1][ 1][ 1]=0, dp[ 1][ 1][ 0 ]=1（符号 F） dp[ 2][ 2][ 1]=1, dp[ 2][ 2][ 0 ]=0（符号 T） dp[ 3][ 3][ 1]=0, dp[ 3][ 3][ 0 ]=1（符号 F）计算区间 [ 0,1 ]（运算符 '|'）： True_ count = 1 1 + 0 0 + 1 1 = 2（左真右假、左真右真） False_ count = 0 1 = 1（左假右假？需核对：实际为左假右假=0 1=0，但左真右假等已算入真？这里应修正为：False_ count = left_ False right_ False = 0 1=0，True_ count=1 1+0 0+1 1=2？）修正计算：正确计算： True = left_ True right_ False + left_ False right_ True + left_ True right_ True = 1 1 + 0 0 + 1 1 = 2 False = left_ False right_ False = 0 1 = 0 因此 dp[ 0][ 1][ 1]=2, dp[ 0][ 1][ 0 ]=0。逐步计算更大区间，最终得到 dp[ 0][ 3][ 1 ] 即为答案。复杂度分析时间复杂度：O(n³)，需要三重循环（区间长度、起始点、分割点）。空间复杂度：O(n²)，用于存储 dp 表。