Recentemente mi sono imbattuto in questa domanda: "Ti viene data un'espressione booleana costituita da una stringa di simboli 'true', 'false', 'and', 'o', e 'xor'. Contare il numero di modi per parentesi l'espressione in modo tale che valuti a true. Ad esempio, esistono due modi per parentesi "vero e falso xo vero" in modo tale che venga valutato come true. "
Sapevo che si trattava di un problema di programmazione dinamica, quindi ho cercato di trovare una soluzione da sola che fosse la seguente. Supponiamo di avere un'espressione come A.B.C ..... D dove '.' rappresenta una qualsiasi delle operazioni e, o, xor e le lettere maiuscole rappresentano vero o falso. Diciamo che il numero di modi in cui questa espressione della dimensione K per produrre un vero è N. quando un nuovo valore booleano E viene aggiunto a questa espressione ci sono 2 modi per parentesi questa nuova espressione 1. ((ABC .... D) .E) ie. con tutte le parentesi possibili di A.B.C ..... D aggiungiamo E alla fine. 2. (A.B.C. (D.E)) ie. prima valuta D.E e poi trova il numero di modi in cui questa espressione di dimensione K può produrre vero.
Supponiamo che T [K] sia il numero di modi in cui l'espressione con dimensione K produce vero, quindi T [k] = val1 + val2 + val3 dove val1, val2, val3 sono calcolati come segue.
1) quando E è raggruppato con D.
i) Non cambia il valore di D
ii) inversione del valore di D
nel primo caso val1 = T [K] = N. (Poiché si riduce all'espressione iniziale A.B.C .... D). Nel secondo caso rivalutare dp [K] con valore di D invertito e cioè val1.
2) quando E è raggruppato con l'intera espressione.
// val2 contiene il numero di 'true' E produrrà con espressioni che hanno dato 'true' tra tutte le istanze tra parentesi di A.B.C ....... D i) if true.E = true then val2 = N
ii) if true.E = false then val2 = 0
// val3 contiene il numero di 'true' E produrrà con espressioni che hanno dato 'false' tra tutte le istanze tra parentesi di A.B.C ....... D
iii) if false.E = true then val3 = (2 ^ (K-2) - N) = M ie. numero di modi in cui l'espressione con dimensione K produce un falso [2 ^ (K-2) è il numero di modi per parentesi di un'espressione di dimensione K].
iv) if false.E = false then val3 = 0
Questa è l'idea di base che avevo in mente ma quando ho controllato la sua soluzione link l'approccio era completamente diverso. Qualcuno può dirmi che cosa sto sbagliando e come posso migliorare nel risolvere il DP in modo da poter trovare soluzioni come quella sopra me stesso.
Grazie in anticipo.