牛客4469题解：位运算表达式的动态规划求解方案（C++代码详解）

一、题目解读

牛客网4469题要求计算给定位运算表达式（由'0'、'1'与'&'、'|'、'^'运算符组成）得到特定结果（0或1）的不同组合方案数。题目核心在于处理位运算的逻辑组合，需高效算法统计所有可行路径。

二、解题思路

采用动态规划（Dynamic Programming）策略，结合区间DP（Interval DP）解决。首先将表达式分离为数字和运算符序列，再利用三维DP数组记录区间结果，通过状态转移方程计算组合方案。关键思路：

1. 分离数字与运算符，避免直接解析表达式复杂度。

2. 设计三维DP数组dp[i][j][k]（区间i到j结果为k的方案数），利用区间划分降低重复计算。

3. 通过运算符分类讨论，递归组合子区间结果。

三、解题步骤

1. 预处理： 遍历表达式，分离数字存入nums，运算符存入ops，避免字符串解析开销。

2. 初始化DP： 单个数字直接赋值（dp[i][i][num[i]] = 1）。

3. 区间DP迭代：

○ 外层循环控制区间长度（从2开始，处理多数字组合）。

○ 内层循环遍历区间起点、分割点，计算子区间组合。

○ 通过compute函数根据运算符计算最终结果，更新DP值（取模防溢出）。

4. 最终结果：dp[0][n-1][目标结果]。

四、代码与注释

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;       // 非法运算符处理
        }
    }
};

五、总结

本解法通过区间DP将位运算组合问题转化为状态转移优化，时间复杂度O(N^3)，空间复杂度O(N^3)，适用于中等规模数据。关键点：

1. 预处理分离数字减少计算量。

2. 三维DP数组设计避免重复子问题。

3. 取模操作保障结果正确性。

掌握此类动态规划思维对解决表达式类算法题有重要启发。