面试题 08.14. 布尔运算
链接：. - 力扣（LeetCode）
题解：dp[i][j][0/1] 表示，从下标i到下标j之间，满足0/1的情况是多少
class Solution {
public:int countEval(string s, int result) {int size = s.size();if (size <= 0) {return 0;}//std::vector<int> tmp(2, 0);//std::vector<std::vector<int>> tmp2(size, tmp);//std::vector<std::vector<std::vector<int>>> dp(size, tmp2);vector<vector<vector<int>>> dp(size, vector<vector<int>>(size, vector<int>(2, 0)));for (int i = 0; i < size; i += 2) {dp[i][i][s[i]-'0'] = 1;//dp[i][i][0] = (s[i] - '0' == 0) ? 1 : 0;//dp[i][i][1] = (s[i] - '0' == 1) ? 1 : 0;}for (int len = 3; len <= size; len += 2) {for (int i = 0; i + len - 1 < size; i += 2) {int j = i + len - 1;for (int k = i + 1; k <= j-1; k += 2) {cout << s[k] << endl;if (s[k] == '&') {dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0];dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1];} else if (s[k] == '|') {dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][1];dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0];} else {dp[i][j][0] += dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][0];dp[i][j][1] += dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0]; }}}}return dp[0][size-1][result];}
};