表达式得到期望结果的组成种数问题
作者：Grey
原文地址：
题目描述
给定一个只由 0(假)、1(真)、&(逻辑与)、|(逻辑或)、^(异或)五种字符组成的字符串 exp，再给定一个布尔值 desired。返回 exp 能有多少种组合方式，可以达到 desired 的结果。
例如：
exp ="1^0|0|1"，desired = false 只有 1^((0|0)|1) 和 1^(0|(0|1)) 的组合可以得到 false，返回 2；
exp ="1"，desired = false，无组合可以得到 false，返回0。
题目链接见：牛客-表达式得到期望结果的组成种数
暴力解法
首先，我们可以做一次初步过滤，初步判断下 exp 的合法性，代码和注释如下：
// 初步筛选一下exp串的合法性 public static boolean errorFormat(char[] exp, int n) { if ((n & 1) == 0) { // 表达式不能为偶数个长度 return true; } for (int i = 0; i < n; i += 2) { if (exp[i] != '1' && exp[i] != '0') { // 0,2,4,8...n-1位置上一定只能是 1 或者 0 return true; } } for (int i = 1; i < n; i += 2) { if (exp[i] != '|' && exp[i] != '^' && exp[i] != '&') { return true; } } return false; } 定义递归函数
int p(char[] exp, int L, int R, boolean desired) 递归含义表示：exp 这个字符串，从 L 到 R 区间内，可以得到 desired 结果的组合数量是多少。
首先考虑 base case，即：只有一个字符的时候，此时 L == R，
有如下三种情况：
if (L == R) { // 只有一个字符的时候， if (desired && exp[L] == '1') { return 1; } else if (!desired && exp[L] == '0') { return 1; } else { return 0; } } 接下来是普遍情况，分别枚举每个操作符可能在的位置的左右两侧的组合数量，然后做乘积即可，代码如下
for (int i = L + 1; i < R; i++) { if (exp[i] == '&') { if (desired) { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true); } else { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true); } } else if (exp[i] == '|') { if (desired) { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true); } else { res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false); } } else { // exp[i] == '^' if (desired) { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true); } else { res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true); } } } 暴力解法的完整代码如下:
public static int getDesiredNum(String exp, boolean desired) { char[] str = exp.toCharArray(); int N = str.length; if (errorFormat(str, N)) { return 0; } return p(str, 0, N - 1, desired); } // 初步筛选一下exp串的合法性 public static boolean errorFormat(char[] exp, int n) { if ((n & 1) == 0) { // 表达式不能为偶数个长度 return true; } for (int i = 0; i < n; i += 2) { if (exp[i] != '1' && exp[i] != '0') { // 0,2,4,8...n-1位置上一定只能是 1 或者 0 return true; } } for (int i = 1; i < n; i += 2) { if (exp[i] != '|' && exp[i] != '^' && exp[i] != '&') { return true; } } return false; } public static int p(char[] exp, int L, int R, boolean desired) { if (L == R) { if (desired && exp[L] == '1') { return 1; } else if (!desired && exp[L] == '0') { return 1; } else { return 0; } } int res = 0; for (int i = L + 1; i < R; i++) { if (exp[i] == '&') { if (desired) { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true); } else { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true); } } else if (exp[i] == '|') { if (desired) { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true); } else { res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false); } } else { // exp[i] == '^' if (desired) { res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true); } else { res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false); res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true); } } } return res; } 本题中，使用暴力递归解法已经可以 AC。
动态规划解法
上述暴力递归方法中，有三个可变参数 L ， R 和 desired，我们可以定义两个二维数组
int[][] tMap = new int[N][N]; int[][] fMap = new int[N][N]; 其中
tMap[i][j]表示 i 到 j 能组成 true 的数量是多少,即暴力递归中的p(exp,i,j,true)；
fMap[i][j]表示 i 到 j 能组成 false 的数量是多少,即暴力递归中的p(exp,i,j,false)；
这个二维数组的对角线下半区无用。
tMap[i][j] 和 fMap[i][j] 的转移方程可以根据暴力递归方法来实现，完整代码如下：
public static int getDesiredNum(String exp, boolean desired) { char[] str = exp.toCharArray(); int N = str.length; if (errorFormat(str, N)) { return 0; } //tMap[i][j] 表示i到j能组成true的数量是多少，所以对角线下半区无用 int[][] tMap = new int[N][N]; //fMap[i][j] 表示i到j能组成false的数量是多少，所以对角线下半区无用 int[][] fMap = new int[N][N]; for (int i = 0; i < N; i += 2) { // 忽视符号位 tMap[i][i] = str[i] == '1' ? 1 : 0; fMap[i][i] = str[i] == '0' ? 1 : 0; } for (int L = N - 3; L >= 0; L -= 2) { for (int R = L + 2; R < N; R += 2) { for (int i = L + 1; i < R; i += 2) { if (str[i] == '&') { tMap[L][R] += tMap[L][i - 1] * tMap[i + 1][R]; fMap[L][R] += tMap[L][i - 1] * fMap[i + 1][R]; fMap[L][R] += fMap[L][i - 1] * fMap[i + 1][R]; fMap[L][R] += fMap[L][i - 1] * tMap[i + 1][R]; } else if (str[i] == '|') { tMap[L][R] += tMap[L][i - 1] * fMap[i + 1][R]; tMap[L][R] += tMap[L][i - 1] * tMap[i + 1][R]; tMap[L][R] += fMap[L][i - 1] * tMap[i + 1][R]; fMap[L][R] += fMap[L][i - 1] * fMap[i + 1][R]; } else { tMap[L][R] += tMap[L][i - 1] * fMap[i + 1][R]; tMap[L][R] += fMap[L][i - 1] * tMap[i + 1][R]; fMap[L][R] += fMap[L][i - 1] * fMap[i + 1][R]; fMap[L][R] += tMap[L][i - 1] * tMap[i + 1][R]; } } } } return desired ? tMap[0][N - 1] : fMap[0][N - 1]; } public static boolean errorFormat(char[] exp, int n) { if ((n & 1) == 0) { // 表达式不能为偶数个长度 return true; } for (int i = 0; i < n; i += 2) { if (exp[i] != '1' && exp[i] != '0') { // 0,2,4,8...n-1位置上一定只能是 1 或者 0 return true; } } for (int i = 1; i < n; i += 2) { if (exp[i] != '|' && exp[i] != '^' && exp[i] != '&') { return true; } } return false; } 
