如何更好地解决动态编程问题

Question

我最近遇到了这个问题:"你得到一个布尔表达式,由一串符号'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问题,以便我能够提出类似上面给出的解决方案.

提前致谢.