Come migliorare la risoluzione dei problemi di programmazione dinamica

9

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.

    
posta newbie 20.06.2012 - 09:58
fonte

2 risposte

9

La risposta, come con molte cose, è:

Pratica, pratica, pratica.

A proposito, credo che nella tua soluzione sei finito in un vicolo cieco facendo un errore banale molto presto: "Ci sono 2 modi per parentesi questa nuova espressione" - non ce ne sono più di 2? Che ne dici di (A.B.(C.D.E)) , ad esempio?

    
risposta data 20.06.2012 - 10:44
fonte
2

Sono d'accordo con l'occulus che la pratica è più richiesta, vorrei anche aggiungere che è necessario prestare attenzione nel riconoscere gli schemi nei problemi che possono essere risolti usando DP (questo è spiegato abbastanza bene in CLRS)

Puoi trovare problemi di spoj che coinvolgono la programmazione dinamica qui :)

    
risposta data 20.06.2012 - 13:18
fonte

Leggi altre domande sui tag