程序员必备的算法（程序员面试金典08.14）

给定一个布尔表达式和一个期望的布尔结果 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 个

1、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)

func counteval(s string, result int) int {n := len(s)// dp[i][j][0/1] => s[i:j 1]结果为0/1的方法数dp := make([][][2]int, n)for i := 0; i < n; i {dp[i] = make([][2]int, n)}for i := n - 1; i >= 0; i = i - 2 {for j := i; j < n; j = j 2 {if i == j {if s[i] == '0' {dp[i][j][0] } else {dp[i][j][1] }continue}for k := i 1; k < j; k = k 2 { // 枚举操作符for a := 0; a <= 1; a {for b := 0; b <= 1; b {if getValue(a, b, s[k]) == 0 {dp[i][j][0] = dp[i][j][0] dp[i][k-1][a]*dp[k 1][j][b]} else {dp[i][j][1] = dp[i][j][01] dp[i][k-1][a]*dp[k 1][j][b]}}}}}}return dp[0][n-1][result]}func getValue(a, b int, op byte) int {if op == '&' {return a & b} else if op == '|' {return a | b}return a ^ b}

2、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)

func counteval(s string, result int) int {n := len(s)// dp[i][j][0/1] => s[i:j 1]结果为0/1的方法数dp := make([][][2]int, n)for i := 0; i < n; i {dp[i] = make([][2]int, n)}for i := n - 1; i >= 0; i = i - 2 {for j := i; j < n; j = j 2 {if i == j {dp[i][j][s[i]-'0'] continue}for k := i 1; k < j; k = k 2 { // 枚举操作符for a := 0; a <= 1; a {for b := 0; b <= 1; b {temp := getValue(a, b, s[k])dp[i][j][temp] = dp[i][j][temp] dp[i][k-1][a]*dp[k 1][j][b]}}}}}return dp[0][n-1][result]}func getValue(a, b int, op byte) int {if op == '&' {return a & b} else if op == '|' {return a | b}return a ^ b}

3、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)

func counteval(s string, result int) int {n := len(s)// dp[i][j][0/1] => s[i:j 1]结果为0/1的方法数dp := make([][][2]int, n)for i := 0; i < n; i {dp[i] = make([][2]int, n)if i%2 == 0 {dp[i][i][int(s[i]-'0')] }}for length := 2; length <= n; length = length 2 { // 枚举长度for i := 0; i <= n-length; i = i 2 { // 枚举起点j := i length // 确定终点for k := i 1; k < j; k = k 2 { // 枚举操作符for a := 0; a <= 1; a {for b := 0; b <= 1; b {temp := getValue(a, b, s[k])dp[i][j][temp] = dp[i][j][temp] dp[i][k-1][a]*dp[k 1][j][b]}}}}}return dp[0][n-1][result]}func getValue(a, b int, op byte) int {if op == '&' {return a & b} else if op == '|' {return a | b}return a ^ b}

Medium题目，采用动态规划