Jak być lepszym w rozwiązywaniu problemów z programowaniem dynamicznym

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ę.

Odpowiedź, podobnie jak w przypadku wielu rzeczy, brzmi:

Ćwicz, ćwicz, ćwicz.

Nawiasem mówiąc, wierzę, że w swoim rozwiązaniu wpadłeś w ślepy zaułek, bardzo wcześnie popełniając trywialny błąd: „Istnieją dwa sposoby nawiasowania tego nowego wyrażenia” - czy nie ma ich więcej niż 2? Co powiesz (A.B.(C.D.E))na przykład?

Zgadzam się z okulusem, że praktyka jest najbardziej potrzebna, chciałbym również dodać, że musisz zwrócić uwagę na rozpoznawanie wzorców problemów, które można rozwiązać za pomocą DP (wyjaśniono to całkiem dobrze w CLRS)

Możesz znaleźć problemy z spojrzeniem, które dotyczą programowania dynamicznego tutaj :)