我最近遇到了这个问题:"你得到一个布尔表达式,由一串符号'true','false','和','或'和'xor'组成.计算用括号括起来的方法的数量表达式,它将评估为true.例如,有两种方法可以将'true和false xor true'括起来,使其计算结果为true."
我知道这是一个动态编程问题所以我试着自己想出一个解决方案,如下所示.假设我们有一个表达式为ABC .... D,其中'.' 表示任何操作,或者,xor和大写字母表示真或假.让我们说这个大小K表达式产生一个真值的方法的数量是N.当一个新的布尔值E被添加到这个表达式时,有两种方法可以将这个新表达式括起来1.((ABC .... D) .E)即.使用ABC的所有可能的括号....我们在最后添加E. 2.(ABC(DE))即.首先评估DE,然后找到这个大小为K的表达式可以生成的方式的数量.
假设T [K]是具有大小K的表达式产生的方式的数量,则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包含将使用表达式生成的'true'的数量,这些表达式在ABC的所有带括号的实例中给出'true'...... D i)如果true.E = true则val2 = N
ii)如果为true.E = false则val2 = 0
// val3包含将使用表达式生成的'true'的数量,这些表达式在ABC的所有带括号的实例中给出'false'...... D
iii)如果为假.E =真则则val3 =(2 ^(K-2) - N)= M ie.大小为K的表达式产生错误的方式的数量[2 ^(K-2)是用括号表示大小为K的表达式的方式的数量].
iv)如果为false.E = false则val3 = 0
这是我想到的基本想法,但当我检查其解决方案http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf时,方法完全不同.有人能告诉我我做错了什么,我怎样才能更好地解决DP问题,以便我能够提出类似上面给出的解决方案.
提前致谢.
可能重复：
如何在C ++中使用数组？
2d数组是双指针吗？
二维数组和指针
我知道这是一个非常基本的问题，但是没有为我解决任何问题。这就是为什么要在这里发布它。在C ++中考虑声明int x[10];
这是一维数组，其中x是基本指针，它包含数组第一个元素的地址。因此，请x给我该地址并*x提供第一个要素。
同样的声明
int x[10][20];
x这里是什么样的变量。当我做
int **z = x;
编译器说它不能转换int (*)[20]为int **。为什么这样做cout<<x;并cout<<*x;给出相同的值？而且如果我将指针数组声明为
int *p[10];
然后x和p（在其类型上）有区别吗？因为当一个声明int x[10]和int *p那么它是有效的分配x到p，但它不是那么二维数组的情况下？为什么？有人可以帮我清除这个问题，或者在此方面提供很好的参考资料。