题解 | 表达式组成方案

class Expression {
public:
    int countWays(string exp, int len, int ret) {
        vector<int> nums((len + 1) / 2);
        vector<char> ops(len / 2);
        
        // 分离数字和运算符
        for(int i = 0; i < len; i++) {
            if(i % 2 == 0) {
                nums[i/2] = exp[i] - '0';
            } else {
                ops[i/2] = exp[i];
            }
        }
        
        return solve(nums, ops, ret);
    }
    
private:
    int cal(int a, int b, char op) {
        switch(op) {
            case '&': return a & b;
            case '|': return a | b;
            default: return a ^ b;  // '^'
        }
    }
    
    int solve(vector<int>& nums, vector<char>& ops, int target) {
        int n = nums.size();
        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;
        }
        
        // 枚举长度和起点
        for(int len = 2; len <= n; len++) {
            for(int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                // 枚举分割点
                for(int k = i; k < j; k++) {
                    // 计算所有可能的值组合
                    for(int v1 = 0; v1 <= 1; v1++) {
                        for(int v2 = 0; v2 <= 1; v2++) {
                            if(dp[i][k][v1] != 0 && dp[k+1][j][v2] != 0) {
                                int val = cal(v1, v2, ops[k]);
                                dp[i][j][val] = (dp[i][j][val] + 
                                    (long long)dp[i][k][v1] * dp[k+1][j][v2]) % 10007;
                            }
                        }
                    }
                }
            }
        }
        
        return dp[0][n-1][target];
    }
};

public class Expression {
    private int cal(int a, int b, char op) {
        switch(op) {
            case '&': return a & b;
            case '|': return a | b;
            default: return a ^ b;  // '^'
        }
    }
    
    private int solve(int[] nums, char[] ops, int target) {
        int n = nums.length;
        int[][][] dp = new int[n][n][2];
        
        // 初始化单个数字
        for(int i = 0; i < n; i++) {
            dp[i][i][nums[i]] = 1;
        }
        
        // 枚举长度和起点
        for(int len = 2; len <= n; len++) {
            for(int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                // 枚举分割点
                for(int k = i; k < j; k++) {
                    // 计算所有可能的值组合
                    for(int v1 = 0; v1 <= 1; v1++) {
                        for(int v2 = 0; v2 <= 1; v2++) {
                            if(dp[i][k][v1] != 0 && dp[k+1][j][v2] != 0) {
                                int val = cal(v1, v2, ops[k]);
                                dp[i][j][val] = (int)((dp[i][j][val] + 
                                    (long)dp[i][k][v1] * dp[k+1][j][v2]) % 10007);
                            }
                        }
                    }
                }
            }
        }
        
        return dp[0][n-1][target];
    }
    
    public int countWays(String exp, int len, int ret) {
        int[] nums = new int[(len + 1) / 2];
        char[] ops = new char[len / 2];
        
        for(int i = 0; i < len; i++) {
            if(i % 2 == 0) {
                nums[i/2] = exp.charAt(i) - '0';
            } else {
                ops[i/2] = exp.charAt(i);
            }
        }
        
        return solve(nums, ops, ret);
    }
}

# -*- coding:utf-8 -*-



class Expression:
    def cal(self, a, b, op):
        if op == '&': return a & b
        if op == '|': return a | b
        return a ^ b  # '^'
    
    def solve(self, nums, ops, target):
        n = len(nums)
        dp = [[[0] * 2 for _ in xrange(n)] for _ in xrange(n)]
        
        # Initialize single digits
        for i in xrange(n):
            dp[i][i][nums[i]] = 1
            print("Initialize dp[%d][%d][%d] = 1" % (i, i, nums[i]))
        
        # Enumerate length and start point
        for l in xrange(2, n + 1):
            for i in xrange(n - l + 1):
                j = i + l - 1
                print("Processing interval [%d, %d]" % (i, j))
                # Enumerate split points
                for k in xrange(i, j):
                    # Calculate all possible value combinations
                    for v1 in xrange(2):
                        for v2 in xrange(2):
                            if dp[i][k][v1] != 0 and dp[k+1][j][v2] != 0:
                                val = self.cal(v1, v2, ops[k])
                                dp[i][j][val] = (dp[i][j][val] + 
                                    dp[i][k][v1] * dp[k+1][j][v2]) % 10007
                                print("dp[%d][%d][%d] = %d" % (i, j, val, dp[i][j][val]))
        
        print("Final result: %d" % dp[0][n-1][target])
        return dp[0][n-1][target]
    
    def countWays(self, exp, length, ret):
        # Split numbers and operators
        nums = [int(exp[i]) for i in xrange(0, length, 2)]
        ops = [exp[i] for i in xrange(1, length, 2)]
        
        print("Numbers: %s" % nums)
        print("Operators: %s" % ops)
        
        return self.solve(nums, ops, ret)