# How to get better at solving Dynamic programming problems

I recently came across this question: "You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there are two ways to parenthesize 'true and false xor true' such that it evaluates to true."

I knew it is a dynamic programming problem so i tried to come up with a solution on my own which is as follows. Suppose we have a expression as A.B.C.....D where '.' represents any of the operations and, or, xor and the capital letters represent true or false. Lets say the number of ways for this expression of size K to produce a true is N. when a new boolean value E is added to this expression there are 2 ways to parenthesize this new expression 1. ((A.B.C.....D).E) ie. with all possible parenthesizations of A.B.C.....D we add E at the end. 2. (A.B.C.(D.E)) ie. evaluate D.E first and then find the number of ways this expression of size K can produce true.

suppose T[K] is the number of ways the expression with size K produces true then T[k]=val1+val2+val3 where val1,val2,val3 are calculated as follows.

1)when E is grouped with D.

i)It does not change the value of D

ii)it inverses the value of D

in the first case val1=T[K]=N.( As this reduces to the initial A.B.C....D expression ). In the second case re-evaluate dp[K] with value of D reversed and that is val1.

2)when E is grouped with the whole expression.

//val2 contains the number of 'true' E will produce with expressions which gave 'true' among all parenthesized instances of A.B.C.......D i) if true.E = true then val2 = N

ii) if true.E = false then val2 = 0

//val3 contains the number of 'true' E will produce with expressions which gave 'false' among all parenthesized instances of A.B.C.......D

iii) if false.E=true then val3=( 2^(K-2) - N ) = M ie. number of ways the expression with size K produces a false [ 2^(K-2) is the number of ways to parenthesize an expression of size K ].

iv) if false.E=false then val3 = 0

This is the basic idea i had in mind but when i checked for its solution http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf the approach there was completely different. Can someone tell me what am I doing wrong and how can i get better at solving DP so that I can come up with solutions like the one given above myself.

• The question's wrong. `true and (false xor true) = (true and false) xor true` (easily seen by reducing both to `false xor true`). Jun 20, 2012 at 8:54
• Great question! I have to get better to DP too. Some say "ah.. DP is just about a simple recursion". It's not!
– Flo
Jun 21, 2012 at 10:32
• @Florents Tselai just saw your comment. Why do you think it's not? Jan 24, 2014 at 10:47

The answer, as with many things, is:

Practice, practice, practice.

By the way, I believe that in your solution you got into a dead-end by making a trivial mistake really early on: "There are 2 ways to parenthesize this new expression" -- aren't there more than 2? How about `(A.B.(C.D.E))`, for example?

• "How do I get better at doing X?" - "Do X!" ... sounds reasonable ;-) Jun 20, 2012 at 11:36

I agree with occulus that practice is most required, also would like to add that you need to pay attention in recognizing the patterns in problems that can be solved using DP (this is explained pretty well in CLRS)

You can find spoj problems that involve dynamic programming here :)

• please comment before downvote so I can improve :) Jun 20, 2012 at 11:38
• that link doesn't work! Jun 21, 2012 at 0:04