布尔表达式括号排列求值计数优化：求高效算法技巧

你的核心问题在于当前算法枚举所有可能的括号组合（卡特兰数级别的指数复杂度），这对于较长输入必然超时。改用**动态规划（DP）**可以将时间复杂度降至O(n³)，大幅减少计算量。

DP思路详解 #

定义两个二维数组：

• dp[i][j][0]：计算从第i个到第j个布尔值组成的子表达式，结果为false的合法括号排列数量
• dp[i][j][1]：结果为true的数量

基础情况 #

当子表达式只有一个布尔值时（i == j）：

• 若s[i]为't'，则dp[i][i][1] = 1，dp[i][i][0] = 0
• 若s[i]为'f'，则dp[i][i][0] = 1，dp[i][i][1] = 0

状态转移 #

对于每个长度大于1的子表达式i~j，遍历所有可能的分割点k（i ≤ k < j），对应运算符为ops[k]。根据运算符的逻辑，结合左右子表达式的true/false组合数：

• &运算符：结果为true仅当左右都为true；其余情况为false
• |运算符：结果为false仅当左右都为false；其余情况为true
• ^运算符：结果为true仅当左右结果不同；相同则为false

优化后的C++代码 #

#include <vector>
#include <string>
#include <iostream>

using namespace std;

int64_t solve(const string &s, const string &ops) {
    int n = s.size();
    if (n < 2 || ops.size() != n - 1) return 0;

    // dp[i][j][0]: 子表达式i~j结果为false的数量
    // dp[i][j][1]: 子表达式i~j结果为true的数量
    vector<vector<vector<int64_t>>> dp(n, vector<vector<int64_t>>(n, vector<int64_t>(2, 0)));

    // 初始化基础情况
    for (int i = 0; i < n; ++i) {
        if (s[i] == 't') {
            dp[i][i][1] = 1;
            dp[i][i][0] = 0;
        } else {
            dp[i][i][0] = 1;
            dp[i][i][1] = 0;
        }
    }

    // 遍历子表达式长度，从2到n
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len <= n; ++i) {
            int j = i + len - 1;
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;

            // 遍历所有分割点k
            for (int k = i; k < j; ++k) {
                char op = ops[k];
                int64_t left0 = dp[i][k][0], left1 = dp[i][k][1];
                int64_t right0 = dp[k+1][j][0], right1 = dp[k+1][j][1];

                switch(op) {
                    case '&':
                        dp[i][j][1] += left1 * right1;
                        dp[i][j][0] += left0 * right0 + left0 * right1 + left1 * right0;
                        break;
                    case '|':
                        dp[i][j][1] += left1 * right1 + left1 * right0 + left0 * right1;
                        dp[i][j][0] += left0 * right0;
                        break;
                    case '^':
                        dp[i][j][1] += left1 * right0 + left0 * right1;
                        dp[i][j][0] += left1 * right1 + left0 * right0;
                        break;
                }
            }
        }
    }

    return dp[0][n-1][1];
}

int main(int argc, char **argv) {
    cout << solve("ttftfftftf", "|&^&&||^&") << endl;
    return 0;
}

为什么这比原算法好 #

• 时间复杂度：原算法是卡特兰数级别的指数复杂度（O(4ⁿ/n^(3/2))），而DP是O(n³)，对于n=20的输入，前者需要数百万次计算，后者仅8000次。
• 避免冗余：原算法中存储括号模式字符串的开销很大，且很多重复的子表达式会被多次计算，DP则直接缓存每个子表达式的结果，无需重复计算。
• 逻辑简洁：DP直接计算所有可能的组合数，不需要提前终止分支，代码更易维护。

内容的提问来源于stack exchange，提问作者John Ziegler