题目地址：

https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression/description/

给定一个长$n$的合法的布尔表达式$s$（只含$0,1,|,\&$和小括号），允许将$1$变成$0$或者相反，也允许将$|$变成$\&$或者相反。问将该表达式的值取反的最小操作次数。规定括号优先级最高，and和or的优先级相同。

思路是树形DP。一个只有二元运算符的表达式可以用一棵二叉树来表示，而求其值实际上就是在做一个中序遍历。那么我们可以令$f[u][0,1]$为要将$u$子树的值变为$0,1$的最小操作次数。考虑$f[u][0]$，那么可以根据$u$是哪个符号，和左右子树取什么值来分类：
如果$u$是and，那么要变成$0$，可以左$0$右$0$，左$1$右$0$，左$0$右$1$，所以此时： f [ u ] [ 0 ] = min ⁡ { f [ u l ] [ 0 ] + f [ u r ] [ 0 ] , f [ u l ] [ 1 ] + f [ u r ] [ 0 ] , f [ u l ] [ 0 ] + f [ u r ] [ 1 ] } f[u][0]=\min\{f[u_l][0]+f[u_r][0],f[u_l][1]+f[u_r][0],f[u_l][0]+f[u_r][1]\} f[u][0]=min{f[ul​][0]+f[ur​][0],f[ul​][1]+f[ur​][0],f[ul​][0]+f[ur​][1]}如果$u$是and，那么要变成$1$，可以左$1$右$0$变符号，左$0$右$1$变符号，左$1$右$1$，所以此时： f [ u ] [ 1 ] = min ⁡ { f [ u l ] [ 1 ] + f [ u r ] [ 0 ] + 1 , f [ u l ] [ 0 ] + f [ u r ] [ 1 ] + 1 , f [ u l ] [ 1 ] + f [ u r ] [ 1 ] } f[u][1]=\min\{f[u_l][1]+f[u_r][0]+1,f[u_l][0]+f[u_r][1]+1,f[u_l][1]+f[u_r][1]\} f[u][1]=min{f[ul​][1]+f[ur​][0]+1,f[ul​][0]+f[ur​][1]+1,f[ul​][1]+f[ur​][1]}其余情况可以类似讨论。如果$u$为树根，则最终答案即为 max ⁡ { f [ u ] [ 0 ] , f [ u ] [ 1 ] } \max\{f[u][0],f[u][1]\} max{f[u][0],f[u][1]}（因为这两个值必然有$1$个为$0$，对应的是不变的情况，从而另一个一定是答案）。

求表达式的值可以用栈来做，树是不用真建出来的，可以参照用栈求中缀表达式的方法。代码如下：

class Solution {
 public:
#define x first
#define y second
  // pair的x对应的是变成0的最少操作次数，y对应的是变成1的最少操作次数
  stack<pair<int, int>> stk;
  stack<char> ops;

  int minOperationsToFlip(string s) {
    for (char &c : s) {
      if (isdigit(c)) {
        if (c == '0') stk.push({0, 1});
        else stk.push({1, 0});
      } else if (c == '(') ops.push('(');
      else if (c == ')') {
        while (ops.top() != '(') eval();
        ops.pop();
      } else {
        while (ops.size() && ops.top() != '(') eval();
        ops.push(c);
      }
    }

    while (ops.size()) eval();
    return max(stk.top().x, stk.top().y);
  }

  void eval() {
    auto b = stk.top(); stk.pop();
    auto a = stk.top(); stk.pop();
    char c = ops.top(); ops.pop();

    if (c == '&') {
      auto v0 = {a.x + b.x, a.y + b.x, a.x + b.y};
      auto v1 = {a.y + b.y, a.y + b.x + 1, a.x + b.y + 1};
      stk.push({*min_element(v0.begin(), v0.end()), *min_element(v1.begin(), v1.end())});
    } else {
      auto v0 = {a.x + b.x, a.y + b.x + 1, a.x + b.y + 1};
      auto v1 = {a.y + b.y, a.y + b.x, a.x + b.y};
      stk.push({*min_element(v0.begin(), v0.end()), *min_element(v1.begin(), v1.end())});
    }
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

时空复杂度$O(n)$。