1. 题目
给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。
实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
示例 1:
输入: s = "1^0|0|1", result = 0
输出: 2
解释: 两种可能的括号方法是
1^(0|(0|1))
1^((0|0)|1)
示例 2:
输入: s = "0&0&0&1^1|0", result = 1
输出: 10
提示：
运算符的数量不超过 19 个来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/boolean-evaluation-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 区间DP解题
dp？[i][j]表示 区间[i,j]内运算值为？（0 or 1）的方案数- 初始化，每个数字处
dp?[i][i]=1, if s[i]==? - 然后按长度
len递增，求解dp[i][i len] dp[i][i len]的求解可以根据其内部左右两侧的方案乘积得出- 所以分成两部分
dp[i,j],dp[j 2][i len],遍历所有的j，j 1处为运算符 - 然后根据运算符的三种可能，讨论0,1的结果，累加即可
class Solution {
public:
int countEval(string s, int result) {
if(s=="")
return 0;
int i, j, n = s.size(), len;
vector<vector<int>> dp0(n,vector<int>(n,0));
vector<vector<int>> dp1(n,vector<int>(n,0));
//dp？[i][j] 表示 区间[i,j]内运算值为 ？ 的方案数
for(i = 0; i < n; i =2)
{
if(s[i]=='1')
dp1[i][i] = 1;
else
dp0[i][i] = 1;
}
for(len = 2; len <= n-1; len = 2)
{ //按长度递增
for(i = 0; i < n-len; i = 2)
{ //左端点i
for(j = i; j <= i len-2; j =2)
{ //中间端点j
if(s[j 1]=='&')
{
dp1[i][i len] = dp1[i][j]*dp1[j 2][i len];
dp0[i][i len] = dp0[i][j]*dp0[j 2][i len] dp1[i][j]*dp0[j 2][i len] dp0[i][j]*dp1[j 2][i len];
}
else if(s[j 1]=='|')
{
dp1[i][i len] = dp1[i][j]*dp1[j 2][i len] dp1[i][j]*dp0[j 2][i len] dp0[i][j]*dp1[j 2][i len];
dp0[i][i len] = dp0[i][j]*dp0[j 2][i len];
}
else//^
{
dp1[i][i len] = dp1[i][j]*dp0[j 2][i len] dp0[i][j]*dp1[j 2][i len];
dp0[i][i len] = dp0[i][j]*dp0[j 2][i len] dp1[i][j]*dp1[j 2][i len];
}
}
}
}
if(result)
return dp1[0][n-1];
return dp0[0][n-1];
}
};8 ms 7 MB
