最近又要考试，勉励自己复习一些之前学过的！！！
开始使用的是DFS，遍历所有可能的情况，发现超时！
下面的是动态规划的一个模板，dp[i][j][result]表示从s的第i个元素到第个元素，结果为result的方案数。主要是第一层for循环从i到j的长度，长度从小到大，dp可以通过长度小的方案数，推出长度大的方案数。
假如：x|y|z|v
如果知道dp[0][2]和dp[3][5]，那么dp[0][5]也可以推出来。有点分治的思想。把长的分成短的。
class Solution:def countEval(self, s: str, result: int) -> int:n = len(s)if not n: return 0dp = [ [ [0,0] for _ in range(n)] for _ in range(n) ]for i in range(0, n, 2):dp[i][i][0] = int(s[i])^1dp[i][i][1] = int(s[i])print(dp[i][i])for L in range(2, n, 2):for i in range(0, n, 2):j = i + Lif j >= n:breakfor k in range(i+1, j, 2):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]elif s[k] == "|":dp[i][j][0] += dp[i][k-1][0]*dp[k+1][j][0]dp[i][j][1] += dp[i][k-1][1]*dp[k+1][j][1] + dp[i][k-1][0]*dp[k+1][j][1] + dp[i][k-1][1]*dp[k+1][j][0]else:dp[i][j][0] += dp[i][k-1][0]*dp[k+1][j][0] + dp[i][k-1][1]*dp[k+1][j][1]dp[i][j][1] += dp[i][k-1][1]*dp[k+1][j][0] + dp[i][k-1][0]*dp[k+1][j][1]return dp[0][-1][result]