学习目标：

我会持续更新我独特的算法思路，希望能给大家带来不一样的思维拓展！
如果大家感觉有帮助的话，欢迎点赞关注支持哦！
你们的鼓励是我坚持下去的动力！
！！！

学习内容：

牛客网链接

学习时间：

2022.4.4

学习产出：

分析：
1.如下所示，使用范围尝试找规律

2.方法一的方法复杂度很大，其中很大一个原因是之前递归计算过的值并没有保留，而导致重复计算，所以我们可以用动态规划，改dp
建立一张True表存放全部True的情况
建立一张False表存放全部False的情况

using System;class test{    const int MOD = 1000000007;    //const long Max =(long)( Math.Pow(10,9)+7);    static void Main(){string input = Console.ReadLine();  //输入表达式 string bo= Console.ReadLine();   //输入目标逻辑值 bool isdesired = bo == "false" ? false : true; long count= dp(input.ToCharArray(), isdesired); Console.WriteLine(count);}public static long dp(char[] express, bool desired){ if (express.Length == 0|| express == null) {return 0; } if (!IsValid(express)) {     return 0; } //开始dp int length = express.Length; //建立二维尝试模型 //T代表True表 F代表Fasle表 long[,] T = new long[length, length]; long[,] F = new long[length, length]; for (int i = 0; i < length; i += 2) {     T[i, i] = (express[i] == '1' ? 1 : 0);     F[i, i] = (express[i] == '0' ? 1 : 0); } //从左往右，从下往上 //i代表列 我们只需要对偶数列做判断 for (int i = 2; i < length; i += 2) {     //然后我们从下往上，找到对角线位置往上2格的格子     //这个for循环是为了从下往上遍历完这一列     //j代表行 我们只需要对偶数行做判断     for (int j = i - 2; j >= 0; j -= 2)     {  //k是逻辑运算符的位置  for (int k = j; k < i; k += 2)  {      //T[j, (k-1)]是前一个0/1位      //T[(k-1) + 2, i]是当前的0/1位置      //为什么这里的位置这么奇葩？其实仔细分析，我们就会发现      //这两个表达式都是压在对角线上的，对角线就代表当前格子是T还是F      //并且对角线我们是很容易填出来的      if (express[k + 1] == '&')      {   //如果是& 那么T要成立 两边都得为True   T[j, i] += (T[j, k] * T[k + 2, i]);   //如果是& 那么F要成立   //那么当前位置为F的情况下，前面位置T/F都行   //那么当前位置为T的情况下，前面位置F才行   F[j, i] += ((F[j, k] + T[j, k]) * F[k + 2, i] + F[j, k] * T[k + 2, i]);      }      else if (express[k + 1] == '^')      {   //如果是^ 那么要T成立   //那么当前位置为F的情况下，前面位置T才行行   //那么当前位置为T的情况下，前面位置F才行   T[j, i] += (T[j, k] * F[k + 2, i] + F[j, k] * T[k + 2, i]);   //如果是^ 那么要F成立   //那么当前位置为F的情况下，前面位置F才行行   //那么当前位置为T的情况下，前面位置T才行   F[j, i] += (F[j, k] * F[k + 2, i] + T[j, k] * T[k + 2, i]);      }      else if (express[k + 1] == '|')      {   //如果是| 那么要T成立   //那么当前位置为F的情况下，前面位置T才行行   //那么当前位置为T的情况下，前面位置F/T都行   T[j, i] += (T[j, k] * F[k + 2, i] +    (F[j, k] + T[j, k]) * T[k + 2, i]);   //如果是| 那么要F成立   //那么当前位置为F的情况下，前面位置F才行行   //那么当前位置为T的情况下，前面位置啥都不行   F[j, i] += (F[j, k] * F[k + 2, i]);      }      T[j, i] %= MOD;      F[j, i] %= MOD;  }     } } return desired ? T[0, length - 1] : F[0, length - 1];    }public static bool IsValid(char[] express)    { //首先需要判断长度是否是奇数 if (express.Length % 2 == 0) {return false; }//其次判断偶数位是否都是0/1for(long i = 0; i < express.Length; i += 2) {     if (express[i] != '0' && express[i] != '1')     {  return false;     } } //然后判断奇数位是否都是 & ^ | for(long i = 1; i < express.Length; i += 2) {     if (express[i] != '&' && express[i] != '^' && express[i] != '|')     {  return false;     } } return true;    }}