Comment améliorer la résolution des problèmes de programmation dynamique

Je suis récemment tombé sur cette question: "On vous donne une expression booléenne composée d'une chaîne de symboles" vrai "," faux "," et "," ou "et" xor ". Comptez le nombre de façons de mettre entre parenthèses le expression telle qu'elle sera évaluée comme vraie. Par exemple, il existe deux manières de mettre entre parenthèses «vrai et faux xou vrai» de telle sorte qu'elle soit évaluée comme vraie. "

Je savais que c'était un problème de programmation dynamique, j'ai donc essayé de trouver une solution par moi-même qui est la suivante. Supposons que nous ayons une expression comme ABC .... D où '.' représente l'une des opérations et, ou, xor et les lettres majuscules représentent vrai ou faux. Disons que le nombre de façons pour cette expression de taille K de produire un vrai est N. quand une nouvelle valeur booléenne E est ajoutée à cette expression, il y a 2 façons de mettre cette nouvelle expression entre parenthèses 1. ((ABC .... D) .E) ie. avec toutes les parenthèses possibles de ABC .... D nous ajoutons E à la fin. 2. (ABC (DE)) c'est-à-dire. évaluez d'abord DE, puis trouvez le nombre de façons dont cette expression de taille K peut produire vrai.

supposons que T [K] est le nombre de façons dont l'expression de taille K produit vrai alors T [k] = val1 + val2 + val3 où val1, val2, val3 sont calculés comme suit.

1) lorsque E est groupé avec D.

i) Il ne modifie pas la valeur de D

ii) il inverse la valeur de D

dans le premier cas val1 = T [K] = N. (Comme cela se réduit à l'expression ABC ... D initiale). Dans le deuxième cas, réévaluez dp [K] avec la valeur de D inversée et c'est val1.

2) lorsque E est groupé avec l'expression entière.

// val2 contient le nombre de «vrais» E produira avec des expressions qui donneront «vrai» parmi toutes les instances entre parenthèses de ABC ...... D i) si vrai. E = vrai alors val2 = N

ii) si vrai E = faux alors val2 = 0

// val3 contient le nombre de «vrais» que E produira avec des expressions qui ont donné «faux» parmi toutes les instances entre ABC entre parenthèses ...

iii) si faux E = vrai alors val3 = (2 ^ (K-2) - N) = M ie. nombre de façons dont l'expression de taille K produit un faux [2 ^ (K-2) est le nombre de façons de mettre entre parenthèses une expression de taille K].

iv) si faux E = faux alors val3 = 0

C'est l'idée de base que j'avais en tête mais quand j'ai vérifié sa solution http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf l'approche y était complètement différente. Quelqu'un peut-il me dire ce que je fais mal et comment puis-je améliorer la résolution de DP afin que je puisse trouver des solutions comme celle donnée ci-dessus moi-même.

Merci d'avance.

La réponse, comme pour beaucoup de choses, est:

Pratique, pratique, pratique.

Soit dit en passant, je crois que dans votre solution, vous êtes tombé dans une impasse en faisant une erreur banale très tôt: "Il y a 2 façons de mettre cette nouvelle expression entre parenthèses" - n'y en a-t-il pas plus de 2? Que diriez-vous (A.B.(C.D.E)), par exemple?

Je suis d'accord avec l'occulus que la pratique est la plus nécessaire, je voudrais également ajouter que vous devez faire attention à reconnaître les modèles de problèmes qui peuvent être résolus en utilisant DP (cela est expliqué assez bien dans CLRS)

Vous pouvez trouver des problèmes de spoj qui impliquent une programmation dynamique ici :)