Ostatnio natknąłem się na to pytanie: „Otrzymujesz wyrażenie boolowskie składające się z ciągu symboli„ prawda ”,„ fałsz ”,„ i ”,„ lub ”i„ xor ”. Policz liczbę sposobów nawiasowania wyrażenie takie, że będzie miało wartość prawda. Na przykład istnieją dwa sposoby nawiasowania „prawda i fałsz xor prawda”, tak że ma wartość prawda ”.
Wiedziałem, że jest to problem z dynamicznym programowaniem, więc próbowałem samodzielnie znaleźć rozwiązanie, które jest następujące. Załóżmy, że mamy wyrażenie ABC… D, gdzie „.” reprezentuje dowolną z operacji i, lub, xor, a wielkie litery oznaczają prawdę lub fałsz. Powiedzmy, że liczba sposobów, w jakie to wyrażenie K może wygenerować wartość true, to N. Gdy nowa wartość boolowska E zostanie dodana do tego wyrażenia, istnieją 2 sposoby nawiasowania tego nowego wyrażenia 1. ((ABC .... D) .E) tj. ze wszystkimi możliwymi nawiasami ABC .... D dodajemy E na końcu. 2. (ABC (DE)) tj. najpierw oszacuj DE, a następnie znajdź liczbę sposobów, w jakie to wyrażenie wielkości K może wygenerować wartość true.
załóżmy, że T [K] jest liczbą sposobów, w jakie wyrażenie o rozmiarze K daje wartość true, a następnie T [k] = val1 + val2 + val3, gdzie val1, val2, val3 oblicza się w następujący sposób.
1) gdy E jest zgrupowane z D.
i) Nie zmienia wartości D
ii) odwraca wartość D
w pierwszym przypadku val1 = T [K] = N. (Ponieważ redukuje się to do początkowego wyrażenia ABC ... D). W drugim przypadku ponownie oszacuj dp [K] z wartością D odwróconą i to jest val1.
2) gdy E jest zgrupowane z całym wyrażeniem.
// val2 zawiera liczbę „true” E wytworzonych za pomocą wyrażeń, które dały „true” wśród wszystkich nawiasowych wystąpień ABC ...... D i) jeśli true.E = true, to val2 = N
ii) jeśli true.E = false, to val2 = 0
// val3 zawiera liczbę „prawdziwych” E wytworzonych za pomocą wyrażeń, które dały „fałszywe” wśród wszystkich nawiasowanych wystąpień ABC ...... D
iii) jeśli false.E = prawda, to val3 = (2 ^ (K-2) - N) = M tj. liczba sposobów, w jakie wyrażenie o rozmiarze K tworzy fałsz [2 ^ (K-2) to liczba sposobów nawiasowania wyrażenia o rozmiarze K].
iv) jeśli false.E = false, to val3 = 0
Jest to podstawowy pomysł, który miałem na myśli, ale kiedy sprawdziłem jego rozwiązanie, http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf podejście było zupełnie inne. Czy ktoś może mi powiedzieć, co robię źle i jak mogę poprawić się w rozwiązywaniu problemów z DP, aby móc znaleźć rozwiązania takie jak podane powyżej.
Z góry dziękuję.
true and (false xor true) = (true and false) xor true(łatwo zauważyć, redukując oba dofalse xor true).