我最近遇到了这个问题：“给你一个布尔表达式，由一串符号'true'、'false'、'and'、'or'和'xor'组成。计算括号括起来的方法的数量表达式，使其计算结果为真。例如，有两种方法可以将“真假异或真”括起来，使其计算结果为真。”
我知道这是一个动态编程问题，所以我尝试自己想出一个解决方案，如下所示。假设我们有一个表达式为 ABC....D where '.' 表示任何操作，或，xor 和大写字母表示真或假。假设这个大小为 K 的表达式产生真值的方法数是 N。当一个新的布尔值 E 被添加到这个表达式时，有 2 种方法可以给这个新表达式 1 加上括号。 ((ABC....D) .E) 即。在所有可能的 ABC....D 括号中，我们在末尾添加 E。2. (ABC(DE)) 即。首先计算 DE，然后找出这个大小为 K 的表达式可以产生真值的方法的数量。
假设 T[K] 是大小为 K 的表达式产生 true 的方式数，那么 T[k]=val1+val2+val3 其中 val1,val2,val3 的计算如下。
1）当 E 与 D 分组时。
i) 它不会改变 D 的值
ii) 它反转了 D 的值
在第一种情况下 val1=T[K]=N.（因为这简化为初始 ABC...D 表达式）。在第二种情况下，重新评估 dp[K]，将 D 的值反转，即 val1。
2）当 E 与整个表达式分组时。
//val2 包含 E 将产生的“真”的数量，在所有带括号的 ABC 实例中给出“真”的表达式......D i) if true.E = true then val2 = N
ii) 如果 true.E = false 那么 val2 = 0
//val3 包含 'true' E 将在所有带括号的 ABC 实例中使用给出 'false' 的表达式生成的数量......D
iii) 如果 false.E=true 则 val3=( 2^(K-2) - N ) = M 即。大小为 K 的表达式产生错误的方式数 [ 2^(K-2) 是括号大小为 K 的表达式的方式数]。
iv) 如果 false.E=false 则 val3 = 0
这是我想到的基本想法，但是当我检查其解决方案http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf时，方法完全不同。有人能告诉我我做错了什么吗？我怎样才能更好地解决 DP，以便我能想出像上面自己给出的解决方案。
提前致谢。