题目
给定一个布尔表达式和一个期望的布尔结果 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
解题
方法一：动态规划
严格来说这个答案不是动态规划。是分治，利用dp数组，记录之前访问过的结果。
k+=2是因，0或1 和 位运算符是 间隔出现的。
保证每次k出现都是数字0或1，每次k+1都是位运算符。
同时k
class Solution { private: vector<vector<vector<int>>> dp; string s; int dfs(int start,int end,int result){ if(start==end) return s[start]-'0'==result?1:0; if(dp[start][end][result]!=-1)return dp[start][end][result];//记忆化，防止重复访问 int count=0; for(int k=start;k<end;k+=2){ char op=s[k+1]; for(int i=0;i<=1;i++){//00、01、10、11四种情况的和 for(int j=0;j<=1;j++){ if(getBoolAns(i,j,op)==result){ count+=dfs(start,k,i)*dfs(k+2,end,j); } } } } dp[start][end][result]=count; return count; } int getBoolAns(int val1,int val2,char op){ if(op=='&') return val1&val2; if(op=='|') return val1|val2; if(op=='^') return val1^val2; return val1&val2; } public: int countEval(string s, int result) { this->s=s; int n=s.size(); dp=vector<vector<vector<int>>>(n,vector<vector<int>>(n,vector<int>(2,-1))); return dfs(0,n-1,result); } };
换种写法
class Solution { public: int countEval(string s, int result) { int n=s.size(); vector<vector<vector<int>>> dp(n,vector<vector<int>>(n,vector<int>(2,-1))); function<bool(int,int,char)> getBoolAns=[&](int val1,int val2,char op){ if(op=='^') return val1^val2; if(op=='|') return val1|val2; if(op=='&') return val1&val2; return val1&val2; }; function<int(int,int,int)> dfs=[&](int start,int end,int r){ if(start==end) return s[start]-'0'==r?1:0; if(dp[start][end][r]!=-1) return dp[start][end][r]; int count=0; for(int k=start;k<end;k+=2){ char op=s[k+1]; for(int i=0;i<=1;i++){ for(int j=0;j<=1;j++){ if(getBoolAns(i,j,op)==r){ count+=dfs(start,k,i)*dfs(k+2,end,j); } } } } dp[start][end][r]=count; return count; }; return dfs(0,n-1,result); } };
