面试题 08.14.布尔运算

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 个

标签 记忆化搜索 字符串 动态规划

2. 解题

TODO: redo 动态规划 使用一个三维数组dp，dp[i][j][k]表示子串s[i:j+1]通过添加括号最终得到结果为k的方案数。 注意i和j位置都应该是数字，k只能取0或1 要计算dp[i][j]我们只需要考虑从子串s[i:j+1]有多少种拆分为两部分的方案。通过遍历(i,j)范围内的操作符即可。 记操作符下标为k，对于每一个可能的k，我们把前半段 dp[i][k-1] 和后半段dp[k+1][j]的结果按情况添加到dp[i][j]当中