牛客4469题解：布尔表达式方案数的动态规划解法
一、问题理解
牛客4469题要求计算给定布尔表达式(仅含0,1和&|^运算符)通过不同运算顺序得到指定结果(0或1)的方案数。这是一个典型的区间动态规划问题，在编译器优化、逻辑电路设计等领域有重要应用。
二、算法核心思想
使用三维动态规划数组dp[i][j][r]表示区间i到j计算结果为r的方案数：
将表达式分离为操作数数组和运算符数组
枚举所有可能的区间分割点
根据运算符类型组合左右子区间的结果
三、完整代码实现（带注释）
class Expression {
public:
const int MOD = 10007;
int countWays(string exp, int len, int ret) {
// 分离数字和运算符
vector<int> nums;
vector<char> ops;
for (int i = 0; i < len; ) {
if (exp[i] == '0' || exp[i] == '1') {
nums.push_back(exp[i] - '0');
i++;
} else {
ops.push_back(exp[i]);
i++;
}
}
int n = nums.size();
if (n == 0) return 0;
// dp[i][j][0/1]表示区间i到j结果为0/1的方案数
vector<vector<vector<int>>> dp(n,
vector<vector<int>>(n, vector<int>(2, 0)));
// 初始化单个数字的情况
for (int i = 0; i < n; i++) {
dp[i][i][nums[i]] = 1;
}
// 区间DP
for (int l = 2; l <= n; l++) { // 区间长度
for (int i = 0; i + l - 1 < n; i++) { // 区间起点
int j = i + l - 1; // 区间终点
for (int k = i; k < j; k++) { // 分割点
char op = ops[k];
// 计算左右子区间的组合
for (int left = 0; left <= 1; left++) {
for (int right = 0; right <= 1; right++) {
int res = compute(left, right, op);
dp[i][j][res] = (dp[i][j][res] +
dp[i][k][left] * dp[k + 1][j][right]) % MOD;
}
}
}
}
}
return dp[0][n - 1][ret];
}
int compute(int a, int b, char op) {
switch (op) {
case '&':
return a & b;
case '|':
return a | b;
case '^':
return a ^ b;
default:
return 0;
}
}
};四、关键点解析
数据结构分离：
nums数组存储操作数(0/1)
ops数组存储运算符(&|^)
DP数组初始化：
单个数字的区间直接初始化为1
三维数组第三维表示0/1两种结果
区间DP过程：
外层循环枚举区间长度
中层循环枚举区间起点
内层循环枚举分割点
运算符处理：
通过compute函数统一处理三种运算符
模运算防止结果溢出
五、常见问题解答
Q: 为什么使用MOD 10007？ A: 题目要求结果对10007取模，防止大数溢出
Q: 时间复杂度是多少？ A: O(n^3)，三重循环分别对应区间长度、起点和分割点
Q: 如何处理运算符优先级？ A: 本题不考虑优先级，所有运算顺序都可能
原创内容 转载请注明出处
