程序员面试金典 – 面试题 08.14. 布尔运算（区间动态规划）网络Michael是个半路程序员-

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