私は最近、この質問に出くわしました。 true と評価されるような式。たとえば、true と評価されるように 'true and false xor true' を括弧で囲む方法は 2 つあります。
私はそれが動的プログラミングの問題であることを知っていたので、次のような解決策を自分で考え出そうとしました。ABC....D のような式があるとします。は演算のいずれかを表し、and、or、xor および大文字は true または false を表します。サイズ K のこの式が true を生成する方法の数が N であるとしましょう。新しいブール値 E がこの式に追加されると、この新しい式 1 を括弧で囲む方法が 2 つあります。 ((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 式に還元されるため)。2 番目のケースでは、D の値を逆にして dp[K] を再評価します。これが val1 です。
2) E が式全体でグループ化されている場合。
//val2 には、'true' の数が含まれます E は、括弧で囲まれた ABC のすべてのインスタンスの中で 'true' を与える式で生成します......D i) if true.E = true then val2 = N
ii) true.E = false の場合、val2 = 0
//val3 には、括弧で囲まれた ABC のすべてのインスタンスの中で「false」を与える式で E が生成する「true」の数が含まれます......D
iii) false.E=true の場合、val3=( 2^(K-2) - N ) = M ie. サイズ K の式が false になる回数 [ 2^(K-2) は、サイズ K の式を括弧で囲む方法の数]。
iv) false.E=false の場合、val3 = 0
これは私が念頭に置いていた基本的な考え方ですが、その解決策を確認したときhttp://people.csail.mit.edu/bdean/6.046/dp/dp_9.swfアプローチはまったく異なりました。誰かが私が間違っていることを教えてもらえますか?どうすればDPを解決するのが上手になり、上記のような解決策を思いつくことができますか.
前もって感謝します。